哈夫曼树

一、 哈夫曼树的基本概念

• 路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。

• 结点的路径长度：两结点间路径上的分支数。
  

  结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树，但路径长度最短的二叉树不一定是完全二叉树。

• 权（weight）：将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。

• 结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积。

• 树的带权路径长度：树中所有叶子结点的带权路径长度之和。

  

• 哈夫曼树：最优树，带权路径长度（WPL）最短的树。

  “带权路径长度最短”是在“度相同”的树中比较而得的结果，因此有最优二叉树、最优三叉树之称等等。

• 哈夫曼树：最优二叉树，带权路径长度（WPL）最短的二叉树。

  因为构造这种树的算法是由哈夫曼教授于1952年提出的，所以被称为哈夫曼树，相应的算法称为哈夫曼算法。

  

二、 哈夫曼树的构造算法

哈夫曼树中权越大的叶子离根越近。

• 哈夫曼算法（构造哈夫曼树的方法）

  1. 根据n个给定的权值{W₁, W₂, ..., W_n } 构成n课二叉树的森林F = {T₁,T₂, ..., T_n}，其中 T_i 只有一个带权为 W_i 的根结点（整个只有一个结点，即根结点）；

     构造森林全是根

  2. 在 F 中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且设置新的二叉树的根结点的权值为其左右子树上根节点的权值之和；
     选用两小造新树

  3. 在 F 中删除这两棵树，同时将新得到的二叉树加入森林中。

     删除两小添新人

  4. 重复(2)和(3)，直到森林中只有一棵树为止，这颗树即为哈夫曼树。

     重复2、3剩单根

  

  小结：

  1. 哈夫曼树的结点的度数为 0 或 2，没有度为 1 的结点。
  2. 在哈夫曼算法中，初始时有n棵二叉树，要经过 n-1 次合并最终形成哈夫曼树。
  3. 经过 n-1 次合并产生 n-1 个新结点，且这 n-1 个新结点都是具有两个孩子的分支结点。
  4. 可见：哈夫曼树中共有 n+n-1 = 2n-1 个结点，且其所有分支结点的度均不为1。

• 哈夫曼树构造算法的实现

  这里采用顺序存储结构——一维结构数组 HuffmanTree HT;

  结点类型定义：

  typedef struct{
      int weigth;
      int parent,lch,rch;
  }HTNode,*HuffmanTree;
  

  

  ​ 哈夫曼树中共有2n-1 个结点，这里不使用 0 下标的结点，数组大小为2n。

  1. 初始化HT [1......2n-1]：lch = rch = parent = 0;

  2. 输入初始 n 个叶子结点，置HT[1.....n]的weight值；

  3. 进行以下 n -1 次合并，依次产生 n-1 个结点 HT[ i ]，i = n + 1......2n-1：

     1. 在HT[1...i-1]中选两个未被选过（从parent == 0 的结点中选）的weight最小的两个结点 HT[s1] 和 HT[s2]，s1、s2为最小结点下标；
     2. 修改HT[s1] 和 HT[s2]的parent值：HT[s1].parent = i; HT[s2].parent = i;
     3. 修改新产生的HT[ i ]：
        • HT[i].weight = HT[s1].weight + HT[s2].weight；
        • HT[i].lch = s1; HT[i].rch = s2;

  void CreatHuffmanTree(HuffmanTree HT,int n){//构造哈夫曼树
      if(n <= 1)return;
      m = 2*n - 1;//数组共 2n-1 个元素
      HT = new HTNode[m + 1];//0号单元未用，HT[m]表示根结点
      for(i = 1; i <= m; ++i){//将 2n-1 个元素的lch、rch、parent置为0
          HT[i].lch = 0;
          HT[i].rch = 0;
          HT[i].parent = 0;
      }
      for(i = 1; i <= n; ++i){
          cin>>HT[i].weight;//输入前 n 个元素的weight值
      }
  //初始化结束，下面开始建立哈夫曼树
  	for( i = n + 1; i <= m; i++){//合并产生 n-1 个结点——构造Huffman树
      Select(HT,i-1,s1,s2);//在HT[k](1<= k <= i-1)中选择两个其双亲域为0，且权值最小的结点，并返回他们在HT中的序号s1和s2
          
          HT[s1].parent = i; HT[s2].parent = i;//表示从F中删除s1，s2
          
          HT[i].lch = s1; HT[i].lch = s2;//s1,s2分别作为 i 的左右孩子
          
          HT[i].weight = HT[s1].weight + HT[s2].weight;//i 的 权值为左右孩子权值之和
  	}
  }
  

  例子：

  

三、哈夫曼编码

前缀编码：任一字符的编码都不是另一个字符的前缀。

问题：什么样的前缀码能使电文总长最短？

方法：

1. 统计字符集中每个字符在电文中出现的平均概率（概率越大，要求编码越短）。

2. 利用哈夫曼树的特点：权越大的叶子离根越近；将每个字符的概率作为权值，构造哈夫曼树。则概率越大的结点，路径越短。

3. 在哈夫曼树的每个分支标上 0 或 1 ：

   结点的左分支标0，右分支标1

   把从根到每个叶子的路径上的标号连接起来，作为该叶子代表的字符编码。

——即哈夫曼编码

• 两个问题：

  1. 为什么哈夫曼编码能够保证是前缀编码？

     因为没有一片叶子是另一片叶子的祖先，所以每个叶结点的编码就不可能是其他叶结点编码的前缀。

  2. 为什么哈夫曼编码能够保证字符编码总长最短？

     因为哈夫曼树的带权路径长度最短，故字符编码大的总长最短。

• 两个性质：

  1. 性质1：哈夫曼编码是前缀编码
  2. 性质2：哈夫曼编码是最优前缀码

• 哈夫曼编码算法实现

  

  void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n){
        //从叶子到根逆向求每一个字符的哈夫曼编码，存储在编码表HC中
        HC = new char *[n+1];//分配n个字符编码的头指针
        cd = new char[n];//分配临时存放编码的动态数组空间
        cd[n-1] = '\0';//编码结束符
        for(i = 1; i <= n; ++i){
            start = n - 1; c = i; f = HT[i].parent;
            while(f! = 0){//从叶子结点开始向上回溯，直到根结点
                --start;//回溯一次start向前指一个位置
                if(HF[f].lchild == c) cd [start] = '0';
                //结点c是f的左孩子，则生成代码0
                else cd[start] = '1';//结点c是f的右孩子，则生成代码0
                c = f; f = HT[f].parent;//继续向上回溯
            }//求出第i个字符的编码
            HC[i] = new char[n - start];//为第i个字符串编码分配空间
            strcpy(HC[i],&cd[start]);//将求得的编码从临时空间cd复制到HC的当前行中
        }
        delet cd;//释放临时空间
    }//CreatHuffmanCode
  

四、文件的编码和解码

1. 编码：
   1. 输入个字符及其权值
   2. 构造哈夫曼树——HT[ i ]
   3. 进行哈夫曼编码——HC[ i ]
   4. 查HC[ i ]，得到各字符的哈夫曼编码
2. 解码：
   1. 构造哈夫曼树
   2. 依次读入二进制码
   3. 读入0，则走向左孩子；读入1，则走向右孩子
   4. 一旦到达某叶子时，即可译出字符
   5. 然后再从根出发继续译码，直到结束