哈夫曼树构造及哈夫曼编码

mastertravels77

前情提要

请为用于通信的电文中的字母进行赫夫曼编码。如各个字母在电文中出现的频率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11。试为这8个字母设计哈夫曼编码。
通信的电文中的字母一般是a,b,c,d,e,f,g,h

根据其出现的概率可设8个字符的权值为：w=（5，29，7，8，14，23，3，11）
将树的左分支标记为0，右分支标记为1，便得到其哈夫曼编码表

代码函数

void CreateHT(HTNode ht[],int n);//构造哈夫曼树
void CreateHCode(HTNode ht[],HCode hcd[],int n);//构造哈夫曼编码
void DispHCode(HTNode ht[],HCode hcd[],int n);//输出哈夫曼编码

代码实现

1. #include<stdio.h>
2. #include<string.h>
3. #define N 50 //叶子节点数
4. #define M 2*N-1 //树中节点总数
5. typedef struct
6. {
7.         char data[5]; //节点值
8.         int weight; //权重
9.         int parent;  //双亲节点
10.         int lchild;  //左孩子节点
11.         int rchild;  //右孩子节点
12. }HTNode;
13. typedef struct
14. {
15.         char cd[N];//存放哈夫曼码
16.         int start;
17. }HCode;
19. void CreateHT(HTNode ht[],int n);//构造哈夫曼树
20. void CreateHCode(HTNode ht[],HCode hcd[],int n);//构造哈夫曼编码
21. void DispHCode(HTNode ht[],HCode hcd[],int n);//输出哈夫曼编码
23. void CreateHT(HTNode ht[],int n)//构造哈夫曼树
24. {
25.         int i,k,lnode,rnode;
26.         int min1,min2;//设置权重最小的两个节点
27.         for(i=0;i<2*n-1;i++)//所有节点的相关域设置初始值为-1
28.         {
29.                 ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
30.         }
31.         for(i=n;i<2*n-1;i++)//构造哈夫曼树
32.         {                      //n前面的空间给输入的值，树的其他节点给算出来的权重和
33.                 min1=min2=32767;//min1为第一个最小的权重，min2为第二个最小的权重
34.                 lnode=rnode=-1;//lnode和rnode为最小权重的两个节点位置
35.                 for(k=0;k<=i-1;k++)
36.                         if(ht[k].parent==-1)//只在尚未构造二叉树的节点中查找
37.                         {
38.                                 if(ht[k].weight<min1)//找权重最小的两个节点
39.                                 {
40.                                         min2=min1;rnode=lnode;//把min1的下标值给了min2,原左孩子的下标lnode给右孩子的下标rnode
41.                                         min1=ht[k].weight;lnode=k;//把权重最小的下标赋给lnode
42.                                 }
43.                                 else if(ht[k].weight<min2)
44.                                 {
45.                                         min2=ht[k].weight;
46.                                         rnode=k;//把权重第二最小的下标赋给rnode
47.                                 }
48.                         }
49.                         ht[lnode].parent=i;ht[rnode].parent=i;//将当前权重最小的两个的双亲节点设为下标为i的节点
50.                         ht[i].weight=ht[lnode].weight+ht[rnode].weight;//下标为i的节点的权重为两个子女的权重和
51.                         ht[i].lchild=lnode;ht[i].rchild=rnode;//设置下标为i的节点的孩子为下标为lnode和rnode
52.                         //注意，设置为孩子的双亲，还要设置双亲的孩子
53.         }
54. }
56. void CreateHCode(HTNode ht[],HCode hcd[],int n)//构造哈夫曼编码
57. {
58.         int i,f,c;
59.         HCode hc;
60.         for(i=0;i<n;i++)//根据哈夫曼树求哈夫曼编码
61.         {
62.                 hc.start=n;c=i;//c获取当前节点的下标
63.                 f=ht[i].parent;//获取输入的叶子节点的双亲节点下标
64.                 while(f!=-1)//循序直到树根节点，树根节点的双亲节点下标为-1
65.                 {
66.                         if(ht[f].lchild==c)//处理左孩子节点，判断当前双亲节点的左孩子是否是节点为c下标，是，就处理
67.                                 hc.cd[hc.start--]='0';//hc.start--从当前节点开始标记0/1一直到根节点
68.                         else               //处理右孩子，判断当前双亲节点的右孩子是否是节点为c下标，是，就处理
69.                                 hc.cd[hc.start--]='1';
70.                         c=f;f=ht[f].parent;//c获取当前节点的下标，f获得双亲节点下标
71.                 }
72.                 hc.start++;//start指向哈夫曼编码最开始字符,最后一次循环产生作用
73.                 hcd[i]=hc;
74.         }
75. }
77. void DispHCode(HTNode ht[],HCode hcd[],int n)//输出哈夫曼编码
78. {
79.         int i,k;
80.         printf("输出哈夫曼编码：\n");
81.         for(i=0;i<n;i++)
82.         {
83.                 printf("       %s:\t",ht[i].data);
84.                 for(k=hcd[i].start;k<=n;k++)
85.                 {
86.                         printf("%c",hcd[i].cd[k]);
87.                 }
88.                 printf("\n");
89.         }
90. }
92. void main()
93. {
94.         int n=8,i;
95.         HTNode ht[M];
96.         HCode hcd[N];
97.         char *str[]={"a","b","c","d","e","f","g","h"};
98.         int fnum[]={5,9,7,8,14,23,3,11};
99.         for(i=0;i<n;i++)
100.         {
101.                 strcpy(ht[i].data,str[i]);
102.                 ht[i].weight=fnum[i];
103.         }
104.         CreateHT(ht,n);
105.         CreateHCode(ht,hcd,n);
106.         DispHCode(ht,hcd,n);
107. }

复制代码

输出