哈夫曼樹構造哈夫曼編碼

august

程序如下：

2. #include<stdio.h>
3. #define MaxSize 50
5. typedef struct
6. {
7.     char data; //結點值
8.     int weight;//權重
9.     int parent;//父結點
10.     int left;  //左結點
11.     int right; //右結點
12. }huffnode;
13. typedef struct
14. {
15.     char cd[MaxSize];
16.     int start;
17. }huffcode;
19. void creahuffman(huffnode ht[],int n) // 構造哈夫曼樹
20. {
21.     int i,k,l,r,m1,m2;
22.     for(i=0;i<2*n-1;i++)
23.         ht[i].parent=ht[i].left=ht[i].right=0;
25.     for(i=n;i<2*n-1;i++)              
26.     {
27.         m1=m2=32767;                 //l,r為最小權重的兩個結點位置
28.         l=r=0;
29.         for(k=0;k<i-1;k++)
30.             if(ht[k].parent==0)
31.                 if(ht[k].weight<m1)
32.                 {
33.                     m2=m1;r=l;
34.                     m1=ht[k].weight;
35.                     l=k;
36.                 }
37.                 else if(ht[k].weight<m2)
38.                 {
39.                     m2=ht[k].weight;
40.                     r=k;
41.                 }
42.                 ht[l].parent=i;ht[r].parent=i;
43.                 ht[i].weight=ht[l].weight+ht[r].weight;
44.                 ht[i].left=l;ht[i].right=r;
45.     }
46. }
48. void creahfcode(huffnode ht[],huffcode hcd[],int n) //求哈夫曼編碼
49. {
50.     int i,f,c;
51.     huffcode d;
52.     for(i=0;i<n;i++)
53.     {
54.         d.start=n+1;c=i;
55.         f=ht[i].parent;
56.         while(f!=0)
57.         {
58.             if(ht[f].left==c)
59.                 d.cd[--d.start]='0';
60.             else
61.                 d.cd[--d.start]='1';
62.             c=f;f=ht[f].parent;
63.         }
64.         hcd[i]=d;
65.     }
66. }
68. void disphuffman(huffnode ht[],huffcode hcd[],int n) //輸出哈夫曼編碼
69. {
70.     int i,k;
71.     printf("輸出哈夫曼編碼：\n");
72.     for(i=0;i<n;i++)
73.     {
74.         printf("%c:",ht[i].data);
75.         for(k=hcd[i].start;k<=n;k++)
76.             printf("%c",hcd[i].cd[k]);
77.         printf("\n");
78.     }
79. }
81. void main()
82. {
83.     int n=6;
84.     huffnode ht[2*MaxSize];
85.     huffcode hcd[MaxSize];
86.     ht[0].data='a'; ht[1].data='b';
87.     ht[2].data='c'; ht[3].data='d';
88.     ht[4].data='e'; ht[5].data='f';
89.     ht[0].weight=10; ht[1].weight=2;
90.     ht[2].weight=6;  ht[3].weight=4;
91.     ht[4].weight=3;  ht[5].weight=1;
93.     creahuffman(ht,n);
94.     creahfcode(ht,hcd,n);
95.     disphuffman(ht,hcd,n);
96. }

复制代码

牠是結點在左子樹上編碼就為0,在右子樹上就為1。
大蝦們能詳細解釋下嗎？我實在是不太理解是怎麼實現的。

诸神的曙光

呃……其实左子树用1右子树用0也可以倒是……就是编码和它相反，平均码长还是一样的……

举个例子吧：
比如有a，b，c，d，e共5个字符，每个字符在某篇文章中，且文章中只含这几个字符（这文章估计很2 - -|）它们出现的概率（即权值）分别为0.2，0.05，0.4，0.25，0.1，现在需要对它们进行2进制编码，原则是出现概率大的编码长度要短，且各个编码不能出现歧义（歧义即为某一个编码的前n个字符为另一个编码）。这个问题思路其实是这样的：

先选两个权值最小的，即b和e，将它们作为一棵树的两个结点，它们的父结点定义为f，那f的权值应该是0.05 + 0.1 = 0.15
再从a，c，d，f中选两个权值最小的（注意现在f是一棵树，其余都只有结点），选出来f和a，再次把二者合成为一颗新树，定义f与a的父结点为g，g的权值为0.15 + 0.2 = 0.35
再从c，d，g中选两个权值最小的……
……
最后会形成一种最优二叉树的结构……然后分别对每个结点的左右分支进行0，1编码，最后就可以得到从root到任意结点的编码

以上是程序的一般思路……

程序主要实现还是在选择2个最小权值子树和将二者合成为一个新子树上……啊，突然有点头晕 ……

august

我差不多忘记了,才有人回答, 以后复习时再看