1、1執行校長李 偉赫夫曼樹及其應用赫夫曼樹及其應用數據結構數據結構( (第十四講第十四講 ) )2課程回顧課程回顧n 樹的存儲結構有哪些？各有什么優缺點？樹的存儲結構有哪些？各有什么優缺點？n 如何實現森林與二叉樹的轉換？如何實現森林與二叉樹的轉換？n 怎樣遍歷森林怎樣遍歷森林?3本講目錄本講目錄n 赫夫曼樹赫夫曼樹n 赫夫曼編碼赫夫曼編碼 基本概念基本概念 構造赫夫曼樹構造赫夫曼樹4本講重點、難點本講重點、難點n 重點重點p赫夫曼樹n 難點難點p赫夫曼編碼5本講目錄本講目錄n 赫夫曼樹赫夫曼樹n 赫夫曼編碼赫夫曼編碼 相關概念相關概念 構造赫夫曼樹構造赫夫曼樹 相關概念相關概念 赫夫曼編碼赫夫

2、曼編碼6赫夫曼樹赫夫曼樹n 赫夫曼樹（最優二叉樹）赫夫曼樹（最優二叉樹）p相關概念路徑：連接從一個結點到另一個結點之間的分支路徑長度：連接兩結點的路徑上的分支數樹的路徑長度：根結點到各結點的路徑長度之和帶權路徑長度：結點到根結點的路徑長度與結點上權 值的乘積樹的帶權路徑長度：樹中所有葉子結點的帶權路徑長 度之和記作：WPL=wklk最優二叉樹：相同條件下，樹的帶權路徑長度最小的 二叉樹7n 示例示例WPL=72+52+22+42=36WPL= 71+52+23+43 =35754225477542WPL=73+53+21+42=46最優二叉樹8n赫夫曼樹的應用赫夫曼樹的應用p在解決某些判定問題

3、時，利用赫夫曼樹可以得到最佳判定算法 p145圖6.23p用于通訊和數據傳送時的赫夫曼編碼9n 構造赫夫曼樹構造赫夫曼樹p由給定的n個權值w1,w2,wn，構造具有n棵二叉樹的森林F = T1,T2,Tn，其中每一棵二叉樹Ti只有一個帶有權值wi的根結點，其左、右子樹均為空。p重復以下步驟, 直到F中僅剩下一棵樹為止：u在F中選取兩棵根結點的權值最小的二叉樹, 做為左、右子樹構造一棵新的二叉樹。置新的二叉樹的根結點的權值為其左、右子樹上根結點的權值之和。u在F中刪去這兩棵二叉樹。u把新的二叉樹加入F。10n 赫夫曼樹的構造過程赫夫曼樹的構造過程 P146 圖圖6.2411n 示例示例: : 已

4、知權值已知權值 W= 5, 6, 2, 9, 7 W= 5, 6, 2, 9, 7 9562752796767913527527169671329527169671312n 赫夫曼編碼赫夫曼編碼p哈夫曼編碼是哈夫曼樹在電訊通信中的應用之一。p通訊中常需要將文字轉換成二進制字符串電文進行傳送。 文字轉換為電文，稱為編碼。p收到電文后要將電文轉換成原來的文字，電文轉換為文字，稱為譯碼。p在電報通信中，電文是以二進制的0，1序列傳送的。在發送端需要將電文中的字符轉換成0，1序列（編碼）發送，在接收端又需要把接收到的0，1序列還原成相應的字符序列（譯碼）。13n 相關概念相關概念p等長編碼 最簡單的二

5、進制編碼方式是等長編碼。假定需傳送的電文最簡單的二進制編碼方式是等長編碼。假定需傳送的電文是是ABACCDAABACCDA ，在電文中僅使用在電文中僅使用A A，B B，C C，D4D4種字符，可依次對種字符，可依次對其編碼為：其編碼為：0000，0101，1010，1111。上述需發送的的電文是。上述需發送的的電文是“00010010101100”。譯碼員可按兩位一組進行譯碼，恢復。譯碼員可按兩位一組進行譯碼，恢復原來的電文。原來的電文。 譯碼時，只需每譯碼時，只需每2位一譯即可。位一譯即可。特點特點：等長等頻率編碼，譯碼容易，但電文不一定最短：等長等頻率編碼，譯碼容易，但電文不一定最短。

6、A B C D00 01 10 11編碼方案編碼方案114p不等長編碼 使用頻度較高的字符分配一個相對比較短的編碼，使用頻度較低的字符分配一個比較長的編碼。 需發送的電文為 “000011010” 接收方接到這段電文后無法進行譯碼，因為無法斷定前面4個0是4個A，1個B、2個A，還是2個B，即譯碼不唯一，因此這種編碼方法不可使用。 A B C D0 00 1 01編編碼方案碼方案2：15p前綴編碼u任何一個字符的編碼都不是同一字符集中另一個字符的編碼的前綴。u利用赫夫曼樹可以構造一種不等長的二進制編碼，并且構造所得的赫夫曼編碼是一種最優前綴編碼，即使所傳電文的總長度最短。 則上述文字的電文為“

7、0110010101110” 共13位。 A B C D0 110 10 111編碼方案編碼方案3：16n 赫夫曼編碼赫夫曼編碼 設有n種字符，每種字符出現的次數為Wi , 其編碼長度為Li (i=1,2,n)， 則整個電文總長度為 Wi Li ， 要得到最短的電文，即使得 Wi Li最小。 也就是以字符出現的次數為權值，構造一棵Huffman樹，并規定左分支編碼位0，右分支編碼為1，則字符的編碼就是從根到該字符所在的葉結點的路徑上的分支編號序列。 用構造Huffman樹編出來的碼，稱為Huffman編碼。17n 示例：示例：設給出一段報文：CAST CAST SAT AT A TASAp字符

8、集合是 C, A, S, T ，各個字符出現的頻度(次數)是 W 2, 7, 4, 5 。p以它們為各葉結點上的權值，建立赫夫曼樹。p左分支賦 0，右分支賦 1，得赫夫曼編碼(變長編碼)。p A : 0 T : 10 C : 110 S : 111p 赫夫曼編碼是一種無前綴的編碼。解碼時不會混淆。18n 赫夫曼樹和赫夫曼編碼的存儲表示赫夫曼樹和赫夫曼編碼的存儲表示typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree; / / 動態分配數組存儲赫夫曼樹/ / typedef char *HuffmanCode; / / 動態分配數組存儲赫夫曼編碼表/ /n 赫夫曼編碼的算法實現（見赫夫曼編碼的算