1、赫夫曼樹的特點,1.權值越大的葉子離根越近，權值越小的葉結點越遠離根結點。 2.具有n個葉子結點的赫夫曼樹共有2n-1個節(jié)點。 3.赫夫曼樹中沒有度為1 的結點。 嚴格的二叉樹：沒有度為1 的結點的二叉樹。,三、哈夫曼樹的構造算法,設置一個結構數(shù)組HuffmanTree保存哈夫曼樹中各結點的信息，數(shù)組元素的結構形式如下： typedef struct unsingned int weight; unsingned int parent,lchild,rchild; HTNode,*HuffmanTree; /動態(tài)分配數(shù)組存儲哈夫曼樹，0號單元不用 Typedef char * *Huffman

2、Code;/動態(tài)分配數(shù)組存儲哈夫曼編碼,其中，weight域保存結點的權值，lchild和rchild域分別保存該結點的左、右孩子結點在數(shù)組HuffmanTree中的序號，從而建立起結點之間的關系。為了判定一個結點是否已加入到要建立的哈夫曼樹中，可通過parent域的值來確定。初始時parent的值為0，當結點加入到樹中時，該結點parent的值為其雙親結點在數(shù)組HuffmanTree中的序號，就不會是0了。 構造哈夫曼樹時，首先將由n個字符形成的n個葉結點存放到數(shù)組HuffmanTree的前n個分量中，然后根據(jù)前面介紹的哈夫曼方法的基本思想，不斷將兩個小子樹合并為一個較大的子樹，每次構成的新

3、子樹的根結點順序放到HuffmanTree數(shù)組中的前n個分量的后面。,void HaffmanTree(HuffmanTree /*輸入n個葉子結點的權值*/,for (i=n+1;i=m;i+) /*構造哈夫曼樹*/ s1=s2=0; m1=m2= 10000; /*取最大權值為10000*/ for (j=1;j=i-1;j+) if (HTj.weightm1 /*查找權值最小且parent為0的兩棵子樹的序號s1 s2*/,/*將找出的兩棵子樹合并為一棵子樹*/ HTs1.parent=i; HT s2.parent=i; HTi.lchild=s1; HTi.rchild=s2; H

4、Ti.weight= HT s1.weight+HT s2.weigh; ,四、哈夫曼樹在編碼問題中的應用,在數(shù)據(jù)通訊中，經(jīng)常需要將傳送的文字轉換成由二進制字符0，1組成的二進制串，我們稱之為編碼。例如，假設要傳送的電文為ABACCDA，電文中只含有A，B，C，D四種字符， 字符的四種不同的編碼方案 字符 編碼 字符 編碼 字符 編碼 字符 編碼 A 000 A 00 A 0 A 01 B 010 B 01 B 110 B 010 C 100 C 10 C 10 C 001 D 111 D 11 D 111 D 10 總電文長度為21 長度為14 長度僅為13,前綴編碼:指的是，任何一個字符的

5、編碼都不是同一字符集中另一個字符的編碼的前綴。,利用赫夫曼樹可以構造一種不等長的二進制編碼，并且構造所得的赫夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長度最短。,如何設計一種編碼，使得電文的總長度最短呢？,具體做法如下：設需要編碼的字符集合為d1，d2，dn，它們在電文中出現(xiàn)的次數(shù)或頻率集合為w1，w2，wn，以d1，d2，dn作為葉結點，w1，w2，wn作為它們的權值，構造一棵哈夫曼樹，規(guī)定哈夫曼樹中的左分支代表0，右分支代表1，則從根結點到每個葉結點所經(jīng)過的路徑分支組成的0和1的序列便為該結點對應字符的編碼，我們稱之為哈夫曼編碼。 在哈夫曼編碼樹中，樹的帶權路徑長度的含義是各個字符的碼長

6、與其出現(xiàn)次數(shù)的乘積之和，也就是電文的代碼總長，所以采用哈夫曼樹構造的編碼是一種能使電文代碼總長最短的不等長編碼。,采用哈夫曼樹進行編碼，則不會產(chǎn)生二義性問題。因為，在哈夫曼樹中，每個字符結點都是葉結點，它們不可能在根結點到其它字符結點的路徑上，所以一個字符的哈夫曼編碼不可能是另一個字符的哈夫曼編碼的前綴，從而保證了譯碼的非二義性。 實現(xiàn)哈夫曼編碼的算法可分為兩大部分： （1）構造哈夫曼樹； （2）在哈夫曼樹上求葉結點的編碼。,求哈夫曼編碼，實質上就是在已建立的哈夫曼樹中，從葉結點開始，沿結點的雙親鏈域回退到根結點，每回退一步，就走過了哈夫曼樹的一個分支，從而得到一位哈夫曼碼值，由于一個字符的哈

7、夫曼編碼是從根結點到相應葉結點所經(jīng)過的路徑上各分支所組成的0，1序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼為所求編碼的高位碼。,/郝夫曼數(shù)和豪夫曼編碼的存儲表示 typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanCode; Typedef char * * HuffmanCode;,Void HuffmanCoding(HuffmanTree ,/從葉子到根你想球每個字符的郝夫曼編碼 HC=(HuffmanCode)malloc(n+1)*sizeof(

8、char*); cd=(char *)malloc(n*sizeof(char); cdn-1=“0”; for (i=1;i=n;i+) /*求每個葉子結點的哈夫曼編碼*/ start=n-1; c=i; p=HTc.parent; while(p!=0) /*由葉結點向上直到樹根*/ if (HTp.lchild= =c ) cd.-start=“0”; else cd.-start=“1”; c=p; p=HTc.parent; ,HCi=(char *)malloc(n-start)*sizeof(char); Strcopy(HCi, ,6假設用于通信的電子由字符集a,b,c,d,e

9、,f,g,h中的字母構成，這8個字母在電文中出現(xiàn)的概率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10 （1）為這8個字母設計哈夫曼編碼。 （2）若用三位二進制數(shù)（07）對這個8個字母進行等長編碼，則哈夫曼編碼的平均碼長是等長編碼的百分之幾？它使電文總長平均壓縮多少？,例題,32,21,19,7,10,6,2,3,0,1,0,0,0,0,0,0,1,1,1,1,1,1,f,c,d,h,a,e,g,b,a:1100 b:00 c:11110 d:1110 e:10 f:11111 g:01 h:1101,哈夫曼編碼碼長： 4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.1=2.7