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

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

算法思路：

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

1. 结构定义和头文件

    1 #include <stdio.h>
    2  #include <malloc.h>
    3  #include <stdlib.h>
    4  #include <string.h>
    5  ​
    6  #define overflow -1
    7  ​
    8  typedef struct {
    9      int weight;//结点权值
   10      int lchild, rchild, parent;//结点左、右孩子、父结点
   11  }hnode,*htree;

    

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

   这部分我先找到前两个无父结点的结点位置赋给p1和p2，再继续遍历之后的与当前的p1和p2位置的结点权值比较

   • 若结点有父结点，直接跳过

   • 若结点无父结点，且权值小于p1，则将该位置赋给p1，令p2等于之前的p1

   • 若结点无父结点，且权值大于p1、小于p2，则将该位置赋给p2

    1  void selectmin(htree ht,int length, int* p1, int* p2) {//搜索当前数组中无父结点的权值最小的两个结点的下标
    2      int i = 1;//数组下标从1开始，0不用
    3  ​
    4      while (ht[i].parent!= 0 && i <= length)//遍历到第一个无父结点的结点位置
    5          i++;
    6      *p1 = i;        i++;
    7      while (ht[i].parent!= 0 && i <= length)//遍历到第二个无父结点的结点位置
    8          i++;
    9      *p2 = i;        i++;
   10  ​
   11      if (ht[*p1].weight > ht[*p2].weight) {//令p1始终指向较小权值的结点位置
   12          int temp = *p1;
   13          *p1 = *p2;
   14          *p2 = temp;
   15      }
   16  ​
   17      for (int n = i; n <= length; n++) {//继续遍历,比较之后的无父结点的结点权值与p1、p2
   18          if (ht[n].parent != 0)//若该结点有父结点，直接跳过
   19              continue;
   20          else if (ht[n].weight < ht[*p1].weight) {//若该结点权值小于p1，令p1等于n，p2等于p1
   21              *p2 = *p1;
   22              *p1 = n;
   23          }
   24          else if (ht[n].weight > ht[*p1].weight&& ht[n].weight < ht[*p2].weight)//若该结点权值大于p1，小于p2，令*p2=n
   25              *p2 = n;
   26      }
   27  ​
   28      return;
   29  }

    

3. 构建哈夫曼树

    1  void createhuffmantree() {//构建哈夫曼树
    2      int lnode;//哈夫曼树叶子结点数
    3      printf("input leafnode number:");
    4      scanf_s("%d", &lnode);
    5      int length=2*lnode-1;//哈夫曼树结点数=2*叶子节点数-1
    6  ​
    7      htree ht = (htree)malloc(sizeof(hnode) * (length + 1));//数组下标从1开始，所以分配(length+1)大小空间
    8      if (!ht)        exit(overflow);
    9      memset(ht, 0, sizeof(hnode) * (length + 1));//将数组内元素都初始化为0
   10  ​
   11      htree p = ht;
   12      for (int i = lnode + 1; i <=length; i++) {//把所有非叶子节点的结点权值规定为无穷大，否则会影响接下来选择结点最小值
   13          (p + i)->weight = 65535;
   14      }
   15  ​
   16  ​
   17      printf("input leafnode weight:");
   18      for (int i = 1; i <= lnode; i++) {//输入叶子结点权值
   19          scanf_s("%d", &(p+i)->weight);
   20      }
   21  ​
   22      int p1, p2;
   23      for (int i = lnode+1; i <= length; i++) {//从第一个非叶子结点开始遍历
   24          selectmin(p, length, &p1, &p2);
   25          (p + i)->lchild = p1;//修改左子树的值
   26          (p + i)->rchild = p2;//修改左子树的值
   27          (p + i)->weight = (p + p1)->weight + (p + p2)->weight;//修改权值
   28          (p + p1)->parent = i;//修改左子树的父结点值
   29          (p + p2)->parent = i;//修改右子树的父结点值
   30      }
   31  ​
   32      for (int i = 1; i <= length; i++) {
   33          printf("%3d    %3d   %3d   %3d   %3d\n", i, (p + i)->weight, (p + i)->parent, (p + i)->lchild, (p + i)->rchild);//遍历输出
   34      }
   35  ​
   36      return;
   37  }

    

4. 主函数及具体实例

   1  int main() {
   2  ​
   3      createhuffmantree();
   4      return 0;
   5  }

    

自我总结

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