哈夫曼树的构建（C语言）

哈夫曼树的构建（C语言）

算法思路：

主要包括两部分算法，一个是在数组中找到权值最小、且无父结点两个结点位置，因为只有无父结点才能继续组成树； ​ 另一个就是根据这两个结点来修改相关结点值。

1. 结构定义和头文件

    #include <stdio.h>
   
     #include <malloc.h>
   
     #include <stdlib.h>
   
     #include <string.h>
   
     ​
   
     #define OVERFLOW -1
   
     ​
   
     typedef struct {
   
         int weight;//结点权值
   
         int lchild, rchild, parent;//结点左、右孩子、父结点
   
     }HNode,*HTree;

2. 在数组中找到目前权值最小的两个结点 由于哈夫曼树规定结点左子树权值小于右子树，所以我这里把权值较小的那个结点位置赋给p1

     void selectMin(HTree HT,int length, int* p1, int* p2) {//搜索当前数组中无父结点的权值最小的两个结点的下标
   
         int i = ;//数组下标从1开始，0不用
   
     ​
   
         while (HT[i].parent!=  && i <= length)//遍历到第一个无父结点的结点位置
   
             i++;
   
         *p1 = i;        i++;
   
         while (HT[i].parent!=  && i <= length)//遍历到第二个无父结点的结点位置
   
             i++;
   
         *p2 = i;        i++;
   
     ​
   
         if (HT[*p1].weight > HT[*p2].weight) {//令p1始终指向较小权值的结点位置
   
             int temp = *p1;
   
             *p1 = *p2;
   
             *p2 = temp;
   
         }
   
     ​
   
         for (int n = i; n <= length; n++) {//继续遍历,比较之后的无父结点的结点权值与p1、p2
   
             if (HT[n].parent != )//若该结点有父结点，直接跳过
   
                 continue;
   
             else if (HT[n].weight < HT[*p1].weight) {//若该结点权值小于p1，令p1等于n，p2等于p1
   
                 *p2 = *p1;
   
                 *p1 = n;
   
             }
   
             else if (HT[n].weight > HT[*p1].weight&& HT[n].weight < HT[*p2].weight)//若该结点权值大于p1，小于p2，令*p2=n
   
                 *p2 = n;
   
         }
   
     ​
   
         return;
   
     }

3. 构建哈夫曼树

     void createHuffmanTree() {//构建哈夫曼树
   
         int lnode;//哈夫曼树叶子结点数
   
         printf("input leafnode number:");
   
         scanf_s("%d", &lnode);
   
         int length=*lnode-;//哈夫曼树结点数=2*叶子节点数-1
   
     ​
   
         HTree HT = (HTree)malloc(sizeof(HNode) * (length + ));//数组下标从1开始，所以分配(length+1)大小空间
   
         if (!HT)        exit(OVERFLOW);
   
         memset(HT, , sizeof(HNode) * (length + ));//将数组内元素都初始化为0
   
     ​
   
         HTree p = HT;
   
         for (int i = lnode + ; i <=length; i++) {//把所有非叶子节点的结点权值规定为无穷大，否则会影响接下来选择结点最小值
   
             (p + i)->weight = ;
   
         }
   
     ​
   
     ​
   
         printf("input leafnode weight:");
   
         for (int i = ; i <= lnode; i++) {//输入叶子结点权值
   
             scanf_s("%d", &(p+i)->weight);
   
         }
   
     ​
   
         int p1, p2;
   
         for (int i = lnode+; i <= length; i++) {//从第一个非叶子结点开始遍历
   
             selectMin(p, length, &p1, &p2);
   
             (p + i)->lchild = p1;//修改左子树的值
   
             (p + i)->rchild = p2;//修改左子树的值
   
             (p + i)->weight = (p + p1)->weight + (p + p2)->weight;//修改权值
   
             (p + p1)->parent = i;//修改左子树的父结点值
   
             (p + p2)->parent = i;//修改右子树的父结点值
   
         }
   
     ​
   
         for (int i = ; i <= length; i++) {
   
             printf("%3d    %3d   %3d   %3d   %3d\n", i, (p + i)->weight, (p + i)->parent, (p + i)->lchild, (p + i)->rchild);//遍历输出
   
         }
   
     ​
   
         return;
   
     }

4. 主函数及具体实例

     int main() {
   
     ​
   
         createHuffmanTree();
   
         return ;
   
     }

自我总结

写这部分时候动态数组分配和使用那里耗了点时间，主要原因还是不太熟以及vs的操作太迷了。经过这次训练又加深了一点理解，vs的调试也逐渐能够熟练使用了，还是挺开心的。