【数据结构】哈弗曼树的算法实现

wander

哈弗曼树中结点结构构建哈夫曼树时，首先需要确定树中结点的构成。由于哈夫曼树的构建是从叶子结点开始，不断地构建新的父结点，直至树根，所以结点中应包含指向父结点的指针。但是在使用哈夫曼树时是从树根开始，根据需求遍历树中的结点，因此每个结点需要有指向其左孩子和右孩子的指针。

所以，哈夫曼树中结点构成用代码表示为：

• //哈夫曼树结点结构
• typedef struct {
•     int weight;//结点权重
•     int parent, left, right;//父结点、左孩子、右孩子在数组中的位置下标
• }HTNode, *HuffmanTree;
  

构建哈弗曼树的算法实现构建哈夫曼树时，需要每次根据各个结点的权重值，筛选出其中值最小的两个结点，然后构建二叉树。

查找权重值最小的两个结点的思想是：从树组起始位置开始，首先找到两个无父结点的结点（说明还未使用其构建成树），然后和后续无父结点的结点依次做比较，有两种情况需要考虑：

• 如果比两个结点中较小的那个还小，就保留这个结点，删除原来较大的结点；
• 如果介于两个结点权重值之间，替换原来较大的结点；
  

实现代码：

• //HT数组中存放的哈夫曼树，end表示HT数组中存放结点的最终位置，s1和s2传递的是HT数组中权重值最小的两个结点在数组中的位置
• void Select(HuffmanTree HT, int end, int *s1, int *s2)
• {
•     int min1, min2;
•     //遍历数组初始下标为 1
•     int i = 1;
•     //找到还没构建树的结点
•     while(HT[i].parent != 0 && i <= end){
•         i++;
•     }
•     min1 = HT[i].weight;
•     *s1 = i;
•     i++;
•     while(HT[i].parent != 0 && i <= end){
•         i++;
•     }
•     //对找到的两个结点比较大小，min2为大的，min1为小的
•     if(HT[i].weight < min1){
•         min2 = min1;
•         *s2 = *s1;
•         min1 = HT[i].weight;
•         *s1 = i;
•     }else{
•         min2 = HT[i].weight;
•         *s2 = i;
•     }
•     //两个结点和后续的所有未构建成树的结点做比较
•     for(int j=i+1; j <= end; j++)
•     {
•         //如果有父结点，直接跳过，进行下一个
•         if(HT[j].parent != 0){
•             continue;
•         }
•         //如果比最小的还小，将min2=min1，min1赋值新的结点的下标
•         if(HT[j].weight < min1){
•             min2 = min1;
•             min1 = HT[j].weight;
•             *s2 = *s1;
•             *s1 = j;
•         }
•         //如果介于两者之间，min2赋值为新的结点的位置下标
•         else if(HT[j].weight >= min1 && HT[j].weight < min2){
•             min2 = HT[j].weight;
•             *s2 = j;
•         }
•     }
• }
  

注意：s1和s2传入的是实参的地址，所以函数运行完成后，实参中存放的自然就是哈夫曼树中权重值最小的两个结点在数组中的位置。

构建哈弗曼树的代码实现如下：

• //HT为地址传递的存储哈夫曼树的数组，w为存储结点权重值的数组，n为结点个数
• void CreateHuffmanTree(HuffmanTree *HT, int *w, int n)
• {
•     if(n<=1) return; // 如果只有一个编码就相当于0
•     int m = 2*n-1; // 哈夫曼树总节点数，n就是叶子结点
•     *HT = (HuffmanTree) malloc((m+1) * sizeof(HTNode)); // 0号位置不用
•     HuffmanTree p = *HT;
•     // 初始化哈夫曼树中的所有结点
•     for(int i = 1; i <= n; i++)
•     {
•         (p+i)->weight = *(w+i-1);
•         (p+i)->parent = 0;
•         (p+i)->left = 0;
•         (p+i)->right = 0;
•     }
•     //从树组的下标 n+1 开始初始化哈夫曼树中除叶子结点外的结点
•     for(int i = n+1; i <= m; i++)
•     {
•         (p+i)->weight = 0;
•         (p+i)->parent = 0;
•         (p+i)->left = 0;
•         (p+i)->right = 0;
•     }
•     //构建哈夫曼树
•     for(int i = n+1; i <= m; i++)
•     {
•         int s1, s2;
•         Select(*HT, i-1, &s1, &s2);
•         (*HT)[s1].parent = (*HT)[s2].parent = i;
•         (*HT)[i].left = s1;
•         (*HT)[i].right = s2;
•         (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
•     }
• }
  

注意，如果使用此程序，对权重值分别为 2、8、7、6、5 的节点构建哈夫曼树，最终效果如图1(A) 所示。但其实，图 1(B) 中显示的哈夫曼树也满足条件，这两棵树的带权路径长度相同。

图 1 两种哈夫曼树

之所以使用此程序构建的哈夫曼树，是图 1(A) 而不是 4(B)，是因为在构建哈夫曼树时，结点 2 和结点 5 构建的新的结点 7 存储在动态树组中位置，比权重值为 7 节点的存储位置还靠后，所以，在程序继续选择两个权值最小的结点时，直接选择了的叶子结点 6 和 7 。