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

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

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

哈夫曼（Haffman）樹，也稱最優(yōu)二叉樹?！纠?-11】設(shè)給定權(quán)值分別為2，3，5，9的四個結(jié)點，圖7-30構(gòu)造了5個形狀不同的二叉樹。請分別計算它們的帶權(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)路徑長度最小，它的特點是權(quán)值越大的葉結(jié)點越靠近根結(jié)點，而權(quán)值越小的葉結(jié)點則遠離根結(jié)點，事實上它就是一棵最優(yōu)二叉樹。由于構(gòu)成最優(yōu)二叉樹的方法是由D·Haffman

最早提出的，所以又稱為哈夫曼樹。2．為什么要使用哈夫曼樹在分析一些決策判定問題的時候，利用哈夫曼樹，可以獲得最佳的決策算法。例如，要編制一個將百分制數(shù)（n）轉(zhuǎn)換為五級分制的程序。這是一個十分簡單的程序，只要用簡單的條件選擇語句即可完成。如：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%等級bEDCBA表7-1：學(xué)生成績分布表圖7-31(c)判定樹3

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

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

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

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

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

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

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

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

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

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