c14-樹第四講

1、1執(zhí)行校長李 偉赫夫曼樹及其應(yīng)用赫夫曼樹及其應(yīng)用數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)( (第十四講第十四講 ) )2課程回顧課程回顧n 樹的存儲(chǔ)結(jié)構(gòu)有哪些？各有什么優(yōu)缺點(diǎn)？樹的存儲(chǔ)結(jié)構(gòu)有哪些？各有什么優(yōu)缺點(diǎn)？n 如何實(shí)現(xiàn)森林與二叉樹的轉(zhuǎn)換？如何實(shí)現(xiàn)森林與二叉樹的轉(zhuǎn)換？n 怎樣遍歷森林怎樣遍歷森林?3本講目錄本講目錄n 赫夫曼樹赫夫曼樹n 赫夫曼編碼赫夫曼編碼 基本概念基本概念 構(gòu)造赫夫曼樹構(gòu)造赫夫曼樹4本講重點(diǎn)、難點(diǎn)本講重點(diǎn)、難點(diǎn)n 重點(diǎn)重點(diǎn)p赫夫曼樹n 難點(diǎn)難點(diǎn)p赫夫曼編碼5本講目錄本講目錄n 赫夫曼樹赫夫曼樹n 赫夫曼編碼赫夫曼編碼 相關(guān)概念相關(guān)概念 構(gòu)造赫夫曼樹構(gòu)造赫夫曼樹 相關(guān)概念相關(guān)概念 赫夫曼編碼赫夫

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

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

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

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

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

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

8、集合是 C, A, S, T ，各個(gè)字符出現(xiàn)的頻度(次數(shù))是 W 2, 7, 4, 5 。p以它們?yōu)楦魅~結(jié)點(diǎn)上的權(quán)值，建立赫夫曼樹。p左分支賦 0，右分支賦 1，得赫夫曼編碼(變長編碼)。p A : 0 T : 10 C : 110 S : 111p 赫夫曼編碼是一種無前綴的編碼。解碼時(shí)不會(huì)混淆。18n 赫夫曼樹和赫夫曼編碼的存儲(chǔ)表示赫夫曼樹和赫夫曼編碼的存儲(chǔ)表示typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree; / / 動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼樹/ / typedef char *HuffmanCode; / / 動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼編碼表/ /n 赫夫曼編碼的算法實(shí)現(xiàn)（見赫夫曼編碼的算