【算法学习笔记】哈夫曼树的构建和哈夫曼编码的实现代码

- 日理万妓 2022-10-07 11:53 13阅读 0赞

# 介绍 #

哈夫曼（Haffman）这种方法的基本思想如下：  
①由给定的n个权值\{W1，W2，…，Wn\}构造n棵只有一个叶子结点的二叉树，从而得到一个二叉树的集合F=\{T1，T2，…，Tn\}。  
②在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和。  
③在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中。  
④重复②、③两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。

对于同一组给定叶子结点所构造的哈夫曼树，树的形状可能不同，但带权路径长度值是相同的，一定是最小的。

## 哈夫曼树的构建 ##

为了方便操作，用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时，设置一个结构数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，结点的结构形式如下：

weight lchild rchild parent  
其中，weight域保存结点的权值，lchild和rchild域分别保存该结点的左、右孩子结点在数组HuffNode中的序号，从而建立起结点之间的关系。为了判定一个结点是否已加入到要建立的哈夫曼树中，可通过parent域的值来确定。初始时parent的值为-1，**当结点加入到树中时，该结点parent的值为其双亲结点在数组HuffNode中的序号，就不会是-1了**。 构造哈夫曼树时，首先将由n个字符形成的n个叶子结点存放到数组HuffNode的前n个分量中，然后根据前面介绍的哈夫曼方法的基本思想，不断将两个较小的子树合并为一个较大的子树，每次构成的新子树的根结点顺序放到HuffNode数组中的前n个分量的后面。

代码：

#define maxvalue 1e6 //定义最大权值整数常量
    #define maxleaf 1e3 //定义哈夫曼树中结点个数整数常量
    #define maxnode maxleaf*2-1
    typedef struct{ 
    int weight;
    int parent;
    int lchild;
    int rchild;
    }HNodeType;
    HNodeType* HuffTree(){ 
    HNodeType node[maxnode];
    int i,j,n;
    int m1,m2,x1,x2;
    cin>>n;//输入叶子结点个数
    for(int i = 0;i < n;i++)
    { 
    node[i].weight=0;
    node[i].parent=-1;
    node[i].lchild=-1;
    node[i].rchild=-1;//初始化结点
    }
    for(int i = 0;i < n;i++)
    { 
    cin>>node[i].weight;//输入n个叶子结点的权值
    }
    for(int i = 0;i <n-1;i++){ 
    m1=m2=maxvalue;//注意由于需要最小的和次小的两个权值，因此需要设两个变量
    x1=x2=0;//一共n-1个叶节点，一共2n-1个结点
    for(int j=0;j<n+i;j++){ 
    //构造哈夫曼树
    
    if(node[j].weight<m1&&node[j].parent=-1){ 
    m2=m1;
    m1=node[j].weight;
    x2=x1;//保存结点的下标
    x1=j;}
    else if(node[j].weight<m2&&node[j].parent=-1){ 
    m2=node[j].weight;
    x2=j;
    }
    }
    //当结点加入到树中时，该结点parent的值为其双亲结点在数组HuffNode中的序号，就不会是-1了
    //现在合并两棵子树 步骤：更新两棵子树的父节点，修改父节点的权值，修改父节点的左右子树信息
    node[x1].parent=n+i;
    node[x2].parent=n+i;//最小权值的结点和倒数第二小的权值结点的双亲相同
    node[n+i].weight=node[x1].weight+node[x2].weight;//记得更新父结点的权值
    node[n+i].lchild=x1;//修改父节点的子树
    node[n+i].rchild=x2;
    }
    return node;
    }

## 哈夫曼编码 ##

构造编码的时候人们希望解决的两个问题是：  
①编码总长最短。  
②译码的唯一性。 哈夫曼树可用于构造使电文的编码总长最短的编码方案。  
具体做法如下：设需要编码的字符集合为\{d1，d2，…，dn\}，它们在电文中出现的次数或频率集合为\{w1，w2，…，wn\}，以d1，d2，…，dn作为叶子结点，w1，w2，…，wn作为它们的权值，构造一棵哈夫曼树，规定哈夫曼树中的左分支代表0，右分支代表1，则从根结点到每个叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，称为哈夫曼编码。

实现哈夫曼编码的算法可分为两大部分：  
①构造哈夫曼树。  
②在哈夫曼树上求叶结点的编码。  
求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域退回到根结点，每退回一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值。由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求编码的高位码。可以设置一结构数组HuffCode用来存储各字符的哈夫曼编码信息，数组元素的结构如下：  
bit start  
其中，分量bit为一维数组，用来保存字符的哈夫曼编码，start表示该编码在数组bit中的开始位置。所以，对于第i个字符，它的哈夫曼编码存放在HuffCode\[i\].bit中的从HuffCode\[i\].start到n的分量上。  
算法实现；（写法一）

#define maxbit 1e6 //定义编码的最大长度整数常量
    typedef struct{ 
    int bit[maxbit];
    int start;}Hcode;
    void HuffCode(){ 
    node huffnode[maxnode];//node为上面的代码定义的结点类型
    Hcode huffcode[maxcode],cd;//cd为一临时编码结点
    int i,j,c,p;
    huffnode=HuffTree();//HuffTree为上面实现的建立哈夫曼树的函数
    for(int i = 0;i < n;i++)
    { 
    cd.start=n-1;//注意start从n-1开始
    c=i;
    p=node[c].parent;
    
    while(p!=-1)
    { 
    if(node[p].lchild==c)cd.bit[cd.start]=0;
    else cd.bit[cd.start]=1;
    cd.start--;
    c=p;//从叶节点往上
    p=node[c].parent;//p变成c的父节点
    }
    for(j=cd.start+1;j<n;j++)
    { 
    Hcode[i].bit[j]=cd.bit[j];}//保存刚刚求出的叶结点的哈夫曼编码和编码的起始位置
    Hcode[i].start=cd.start;
    }
    for(i=0;i<n;i++)
    { 
    for(j=start+1,j<n;j++)
    cout<<Hcode[i].bit[j];//输出每个叶结点的哈夫曼编码
    }

写法二：

typedef HuffNode{ 
    char data;//待编码的符号
    double weight;//符号出现的频率
    int parent,lchild,rchild;
    }HTnode,*HuffmanTree;

编码：从叶结点回退，左分支记0 右记1

void Code(HuffmanTree &HT,int n,int i,char *code)
    { 
    //求第i个字符的编码
    int p,parent,start;
    char *cd;
    cd = new char[n];
    cd[n-1] = '\0';
    start = n-1;
    p = i;//p是当前结点的下标
    parent = HT[i].parent;//当前结点的父节点下标
    while(parent != -1)
    { 
    if(HT[parent].lchild == p)
    cd[--start] = '0';
    else
    cd[--start] = '1';
    p = parent;
    parent = HT[patent].parent;//沿双亲回退
    }
    strcpy(code,&cd[start]);
    delete[]cd;
    }