數(shù)據(jù)結(jié)構(gòu)之哈夫曼樹及其應(yīng)用

數(shù)據(jù)結(jié)構(gòu)之哈夫曼樹及其應(yīng)用西安航空職業(yè)技術(shù)學(xué)院計(jì)算機(jī)工程學(xué)院：李永鋒7-6

哈夫曼樹及其應(yīng)用7-6-1哈夫曼樹的引入1.概述

哈夫曼（Haffman）樹，也稱最優(yōu)二叉樹?！纠?-11】設(shè)給定權(quán)值分別為2，3，5，9的四個(gè)結(jié)點(diǎn)，圖7-30構(gòu)造了5個(gè)形狀不同的二叉樹。請(qǐng)分別計(jì)算它們的帶權(quán)路徑長度。圖7-30不同二叉樹帶權(quán)路徑長度

五棵樹的帶權(quán)路徑長度分別為：（a）WPL＝2×2＋3×2＋5×2＋9×2＝38（b）WPL＝2×3＋3×3＋5×2＋9×1＝34（c）WPL＝2×2＋3×3＋5×3＋9×1＝37（d）WPL＝9×3＋5×3＋3×2＋2×1＝50（e）WPL＝2×1＋3×3＋5×3＋9×2＝44其中以圖(b)的帶權(quán)路徑長度最小，它的特點(diǎn)是權(quán)值越大的葉結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉結(jié)點(diǎn)則遠(yuǎn)離根結(jié)點(diǎn)，事實(shí)上它就是一棵最優(yōu)二叉樹。由于構(gòu)成最優(yōu)二叉樹的方法是由D·Haffman

最早提出的，所以又稱為哈夫曼樹。2．為什么要使用哈夫曼樹在分析一些決策判定問題的時(shí)候，利用哈夫曼樹，可以獲得最佳的決策算法。例如，要編制一個(gè)將百分制數(shù)（n）轉(zhuǎn)換為五級(jí)分制的程序。這是一個(gè)十分簡單的程序，只要用簡單的條件選擇語句即可完成。如：if(n<60)b=”E”;elseif(n<70)b=”D”elseif(n<80)b=”C”elseif(n<90)b=”B”elseb=”A”;圖7-31(a)判定樹1上述判定過程可以用圖7-31（a）的判定樹來表示圖7-31(b)判定樹2分?jǐn)?shù)n0~5960~6970~7980~8990~100比例數(shù)5%15%40%30%10%等級(jí)bEDCBA表7-1：學(xué)生成績分布表圖7-31(c)判定樹3

若以百分比值5、15、40、30、10為權(quán)構(gòu)造一棵有五個(gè)葉子結(jié)點(diǎn)的哈夫曼樹，則可得到圖7-31（b）所示的判定樹，它使大部分?jǐn)?shù)據(jù)經(jīng)過較少的比較次數(shù)，就能得到換算結(jié)果。由于每個(gè)判定框都有兩次比較，將這兩次比較分開，就可以得到如圖7-31(c)所示的判定樹，按此判定樹編寫出的程序，將大大減少比較的次數(shù)，從而提高運(yùn)算的速度。實(shí)踐證明：

假設(shè)有10000個(gè)輸入數(shù)據(jù):

若按圖7-31（a）的判定過程進(jìn)行操作，則總共需進(jìn)行31500次比較；若按圖7-31（c）的判定過程進(jìn)行操作，則總共僅需進(jìn)行22000次比較。

7-6-2哈夫曼樹的建立1．哈夫曼樹構(gòu)成的基本思想是：（1）由給定的n個(gè)權(quán)值{W1，W2，…，Wn}構(gòu)造n棵只有一個(gè)葉結(jié)點(diǎn)的二叉樹，從而得到一個(gè)二叉樹的集合:

F＝{T1，T2，…，Tn}；（2）在F中選取根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹作為左、右子樹構(gòu)造一棵新的二叉樹，這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和；（3）在集合F中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到集合F中；（4）重復(fù)（2）、（3）兩步，當(dāng)F中只剩下一棵二叉樹時(shí)，這棵二叉樹便是所要建立的哈夫曼樹。動(dòng)畫演示思考：上圖中的權(quán)值6和另一個(gè)生成的權(quán)值7結(jié)合可否生成哈夫曼樹？答：可以，對(duì)于同一組給定葉結(jié)點(diǎn)權(quán)值所構(gòu)造的哈夫曼樹，樹的形狀可能不同，但其帶權(quán)路徑長度值是相同的，而且必定是最小的。

【例7-12】設(shè)結(jié)點(diǎn)的權(quán)集W={10，12，4，7，5，18，2}，建立一棵哈夫曼樹，并求出其帶權(quán)路徑長度。

圖7-33哈夫曼樹的建立過程7-6-3哈夫曼編碼1．什么是哈夫曼編碼？在數(shù)據(jù)通訊中，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符0，1組成的二進(jìn)制代碼，稱之為編碼。如果在編碼時(shí)考慮字符出現(xiàn)的頻率，讓出現(xiàn)頻率高的字符采用盡可能短的編碼，出現(xiàn)頻率低的字符采用稍長的編碼，構(gòu)造一種不等長編碼，則電文的代碼就可能更短。哈夫曼編碼是一種用于構(gòu)造使電文的編碼總長最短的編碼方案。2．求哈夫曼編碼的方法（1）構(gòu)造哈夫曼樹

設(shè)需要編碼的字符集合為{d1，d2，…，dn}，它們?cè)陔娢闹谐霈F(xiàn)的次數(shù)集合為{w1，w2，…，wn}，以d1，d2，…，dn作為葉結(jié)點(diǎn)，w1，w2，…，wn作為它們的權(quán)值，構(gòu)造一棵哈夫曼樹?！纠?-13】設(shè)有A，B，C，D，E，F(xiàn)6個(gè)數(shù)據(jù)項(xiàng)，其出現(xiàn)的頻度分別為6、5、4、3、2、1，構(gòu)造一棵哈夫曼樹，并確定它們的哈夫曼編碼。

圖7-34構(gòu)造哈夫曼樹到哈夫曼編碼的過程（2）在哈夫曼樹上求葉結(jié)點(diǎn)的編碼。規(guī)定哈夫曼樹中的左分支代表0，右分支代表1，則從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)所經(jīng)過的路徑分支組成的0和1的序列便為該結(jié)點(diǎn)對(duì)應(yīng)字符的編碼，如圖7-34（b）編碼為：

A=11；B=01；C=00；D=100；E=1011；F=1010。在哈夫曼編碼樹中，樹的帶權(quán)路徑長度的含義是各個(gè)字符的碼長與其出現(xiàn)次數(shù)的乘積之和，也就是電文的代碼總長。采用哈夫曼樹構(gòu)造的編碼是一種能使電文代碼總長為最短的、不等長編碼。兩個(gè)問題？問題一：采用哈夫曼樹編碼，會(huì)不會(huì)產(chǎn)生二義性？問題二：讀取編碼與存儲(chǔ)編碼相反。問題一：采用哈夫曼樹編碼，會(huì)不會(huì)產(chǎn)生二義性？答：不會(huì)產(chǎn)生上述二義性問題。因?yàn)?，在哈夫曼樹中，每個(gè)字符結(jié)點(diǎn)都是葉結(jié)點(diǎn)，它們不可能在根結(jié)點(diǎn)到其它字符結(jié)點(diǎn)的路徑上，所以一個(gè)字符的哈夫曼編碼不可能是另一個(gè)字符的哈夫曼編碼的前綴，從而保證了譯碼的非二義性。問題二：讀取編碼與存儲(chǔ)編碼相反。答：求哈夫曼編碼，實(shí)質(zhì)上就是在已建立的哈夫曼樹中，從葉結(jié)點(diǎn)開始，沿結(jié)點(diǎn)的雙親鏈域回退到根結(jié)點(diǎn)，每回退一步，就走過了哈夫曼樹的一個(gè)分支，從而得到一位哈夫曼碼值，由于一個(gè)字符的哈夫曼編碼是從根結(jié)點(diǎn)到相應(yīng)葉結(jié)點(diǎn)所經(jīng)過的路徑上各分支所組成的0，1序列，因此先得到的分支代碼為所求編碼的低位碼，后得