本文檔的主要內(nèi)容詳細(xì)介紹的是什么是哈夫曼樹?哈夫曼樹的詳細(xì)資料講解。

　　在計(jì)算機(jī)數(shù)據(jù)處理中，霍夫曼編碼使用變長編碼表對源符號（如文件中的一個字母）進(jìn)行編碼，其中變長編碼表是通過一種評估來源符號出現(xiàn)機(jī)率的方法得到的，出現(xiàn)機(jī)率高的字母使用較短的編碼，反之出現(xiàn)機(jī)率低的則使用較長的編碼，這便使編碼之后的字符串的平均長度、期望值降低，從而達(dá)到無損壓縮數(shù)據(jù)的目的。

　　例如，在英文中，e的出現(xiàn)機(jī)率最高，而z的出現(xiàn)概率則最低。當(dāng)利用霍夫曼編碼對一篇英文進(jìn)行壓縮時，e極有可能用一個比特來表示，而z則可能花去25個比特（不是26）。用普通的表示方法時，每個英文字母均占用一個字節(jié)，即8個比特。二者相比，e使用了一般編碼的1/8的長度，z則使用了3倍多。倘若我們能實(shí)現(xiàn)對于英文中各個字母出現(xiàn)概率的較準(zhǔn)確的估算，就可以大幅度提高無損壓縮的比例。

　　霍夫曼樹又稱最優(yōu)二叉樹，是一種帶權(quán)路徑長度最短的二叉樹。所謂樹的帶權(quán)路徑長度，就是樹中所有的葉結(jié)點(diǎn)的權(quán)值乘上其到根結(jié)點(diǎn)的路徑長度（若根結(jié)點(diǎn)為0層，葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長度為葉結(jié)點(diǎn)的層數(shù)）。樹的路徑長度是從樹根到每一結(jié)點(diǎn)的路徑長度之和，記為WPL=（W1*L1+W2*L2+W3*L3+.。.+Wn*Ln），N個權(quán)值Wi（i=1，2，。..n）構(gòu)成一棵有N個葉結(jié)點(diǎn)的二叉樹，相應(yīng)的葉結(jié)點(diǎn)的路徑長度為Li（i=1，2，。..n）。可以證明霍夫曼樹的WPL是最小的。

　　讓我們先舉一個例子。判定樹：

　　在很多問題的處理過程中，需要進(jìn)行大量的條件判斷，這些判斷結(jié)構(gòu)的設(shè)計(jì)直接影響著程序的執(zhí)行效率。例如，編制一個程序，將百分制轉(zhuǎn)換成五個等級輸出。大家可能認(rèn)為這個程序很簡單，并且很快就可以用下列形式編寫出來：