轉載請注明出處
http://blog.csdn.net/pony_maggie/article/details/41594015
作者:小馬
**一什么是赫夫曼樹**
赫夫曼樹是指帶權路徑最短的樹，從根結點到葉子結點所經過的結點數(不包括根結點，包括葉子結點)叫路徑，如果給葉子結點賦予權值，那么路徑和權值的乘積就是訪問該葉子結點的代價，對于一棵樹來講，使訪問所有的葉子結點的代價最小的樹，就是赫夫曼樹。
比如下面三個圖:
可以計算它們的帶權路徑長度，分別為
(a)????圖是36
(b)????圖是46
(c)????圖是 35
所以c圖是赫夫曼樹。
**二如何構造赫夫曼樹**
構造一棵赫夫曼樹的步驟其實不復雜，簡單來講就是權值大的盡量靠近根結點，而且是越大的越靠近。這樣得出的效果是權值越大的結點，可以經過相對較少的距離到達，從而使程序的效率提高。這里的所說的效率，即包括時間上也包括空間上，后面我會講到兩個應用例子，分別就是一個時間上的優化，一個空間上的優化。
赫夫曼本人給了一個基本的算法，如下:
(1) 將w1、w2、…，wn看成是有n 棵樹的集合F(每棵樹僅有一個根結點)；
(2) 在這些樹中選出兩個根結點的權值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；
(3)從F中刪除選取的兩棵樹，并將新樹加入F
(4)重復(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹
**三應用舉例**
了解的具體的算法之后，必須要知道它的應用場景，不然也就只能停留在理論階段了。這里給出兩個應用的例子。
比如統計一次考試中的學生成績，劃分為5個等級，60分以下為不及格，60到70之間是及格，70到80之間是中等，80到90之間是良好，90到100之間是優秀。本次考試各個階段學生所占比例如下:
| 分數 | 0-59 | 60-69 | 70-79 | 80-89 | 90-100 |
|-----|-----|-----|-----|-----|-----|
| 比例 | 0.05 | 0.15 | 0.40 | 0.30 | 0.10 |
假設有10000個學生，然后我們用下面的代碼來實現統計：
~~~
if (a < 60) b = "不及格";
else if (a < 70) b = "及格";
else if (a < 80) b = "中等";
else if (a < 90) b = "良好";
else b = "優秀";
~~~
代碼對應的樹結構如下:
這樣一共需要比較30000多次。上面的代碼不管你的分數是多少，總要從小于60開始比較，比如一個學生的成績是85，他要被比較四次才能有結果，不幸的是, 大部分學生的成績都是在70到90之間，都要經過至少三次以上的比較才能完成。
如果我們能把這個占大多數人的分數區間放在前面，不就可以大大減少比較的次數了嗎？先按照前面章節講的步驟構造一棵赫夫曼樹，如下圖:
對應的代碼是:
~~~
if (a >= 70 && a < 80) b = "中等";
else if (a >= 80 && a < 90) b = "良好";
else if (a >= 60 && a < 70) b = "及格";
else if (a < 60) b = "不及格";
else b = "優秀";
~~~
這樣比較的次數變為22000次，大大提高效率。
再來一個應用的例子。
電報傳送時，一般要把字符轉成二進制的編碼，比如一串字符, “ABACCDA”, 四種字符，可以用二位表示一種，比如A是00, B是01, C是10, D是11，那么電報發送的就是00010010101100，對方收到電報時可以兩位一組解出來。
上面的方法沒有什么問題，但是一般傳送電報肯定希望能用最短的長度傳遞盡量多的信息，是不是還可以優化呢。當然，我們用不同長度的編碼來表示這些字符，出現次數多的字符盡可能的短，出現次數少的可以偏長一些，這樣可以構造出一個比上面更短的電報編碼。
上面的字符信息，A和C現的次數較多，分別為兩次和三次，B和D都是一次。按照上面的方法來構造一棵赫夫曼樹，如下:
規則是左0右1, 這樣，A是0, B是110, C是10, D是111, 最后的編碼是0110010101110, 一共是13個bit位，原來是14個bit位，確實變短了。
再來看看電報接收的一方收到這串編碼能不能解出來，試一下發現可以正常解析，不會產生歧義。這是因為任意一個字符的編碼都不是另一個字符的編碼前綴。這也是二叉樹本身自帶的一個功能，我們通過這種左0右1的方式得到的編碼就可以達到這種效果。
下篇講如何用代碼實現赫夫曼編碼
