二叉樹的知識還沒完哈，我們來介紹一下哈夫曼樹。
參考部落格：
哈夫曼樹
haffman哈夫曼樹——貪心算法（java）
哈夫曼樹原理，及構造方法
概述
給定n個權值作為n個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近。
首先我們先學會這樣一個概念：樹的帶權路徑長度，用WPL表示
其中，n表示葉子結點的數目，wi和li 分别表示葉子結點的權值和根到該結點之間路徑的長度。
我們着重解釋一下路徑長度，結點的路徑長度，其實就是看從根結點到該結點的分支數，也就是需要查找的次數，如果是根結點的左孩子，查找次數就是1，隻需要與根結點的資訊比較一次即可查到。有些文章管路徑長度叫 構造價值。
了解了這一概念，我們來看一棵樹的WPL，如下grade 1-5 代表學生成績從低到高的五個階段。
同樣這幾個結點，不同的樹結構WPL也是不同的。看上圖，機率極低的grade=1的情況，為何隻查找一次就查到了呢？豈不是很浪費？是以我們想到，讓頻率高的值查找更快。
這就是哈夫曼樹的基本原理。讓查找效率更高，讓出現頻率更高的元素（權重大的），擁有較少的查找次數。
哈夫曼樹的構造
根據以上原理我們再學習哈夫曼樹的構造就容易多了。可以參考上面介紹的部落格。貪心算法來構造即可，從權重小的結點開始合并，不再贅述。
哈夫曼編碼
哈夫曼編碼的知識一般從兩個方面認識：
- 給定一段字元串，如何 對字元進行編碼 ，可以使得該字元串的編碼存儲空間最少？
- 怎麼進行不等長編碼？如何避免二義性？ （字首碼prefix code ：任何字元的編碼都不是另一字元編碼的字首）
我們來看百度百科的介紹，這就是哈夫曼編碼的實際應用及其應用價值。
在計算機資料進行中，哈夫曼編碼使用變長編碼表對源符号（如檔案中的一個字母）進行編碼，其中變長編碼表是通過一種評估來源符号出現機率的方法得到的，出現機率高的字母使用較短的編碼，反之出現機率低的則使用較長的編碼，這便使編碼之後的字元串的平均長度、期望值降低，進而達到無損壓縮資料的目的。
例如，在英文中，e的出現機率最高，而z的出現機率則最低。當利用哈夫曼編碼對一篇英文進行壓縮時，e極有可能用一個比特來表示，而z則可能花去25個比特（不是26）。用普通的表示方法時，每個英文字母均占用一個位元組，即8個比特。二者相比，e使用了一般編碼的1/8的長度，z則使用了3倍多。倘若我們能實作對于英文中各個字母出現機率的較準确的估算，就可以大幅度提高無損壓縮的比例。
在資料通信中，需要将傳送的文字轉換成二進制的字元串，用0，1碼的不同排列來表示字元。例如，需傳送的封包為“AFTER DATA EAR ARE ART AREA”，這裡用到的字元集為“A，E，R，T，F，D”，各字母出現的次數為{8，4，5，3，1，1}。現要求為這些字母設計編碼。要差別6個字母，最簡單的二進制編碼方式是等長編碼，固定采用3位二進制，可分别用000、001、010、011、100、101對“A，E，R，T，F，D”進行編碼發送，當對方接收封包時再按照三位一分進行譯碼。顯然編碼的長度取決封包中不同字元的個數。若封包中可能出現26個不同字元，則固定編碼長度為5。然而，傳送封包時總是希望總長度盡可能短。在實際應用中，各個字元的出現頻度或使用次數是不相同的，如A、B、C的使用頻率遠遠高于X、Y、Z，自然會想到設計編碼時，讓使用頻率高的用短碼，使用頻率低的用長碼，以優化整個封包編碼。
為使不等長編碼為字首編碼(即要求一個字元的編碼不能是另一個字元編碼的字首)，可用字元集中的每個字元作為葉子結點生成一棵編碼二叉樹，為了獲得傳送封包的最短長度，可将每個字元的出現頻率作為字元結點的權值賦予該結點上，顯然字使用頻率越小權值越小，權值越小葉子就越靠下，于是頻率小編碼長，頻率高編碼短，這樣就保證了此樹的最小帶權路徑長度效果上就是傳送封包的最短長度。是以，求傳送封包的最短長度問題轉化為求由字元集中的所有字元作為葉子結點，由字元出現頻率作為其權值所産生的哈夫曼樹的問題。利用哈夫曼樹來設計二進制的字首編碼，既滿足字首編碼的條件，又保證封包編碼總長最短。
哈夫曼靜态編碼：它對需要編碼的資料進行兩遍掃描：第一遍統計原資料中各字元出現的頻率，利用得到的頻率值建立哈夫曼樹，并必須把樹的資訊儲存起來，即把字元0-255(2^8=256)的頻率值以2-4BYTES的長度順序存儲起來，（用4Bytes的長度存儲頻率值，頻率值的表示範圍為0--2^32-1，這已足夠表示大檔案中字元出現的頻率了）以便解壓時建立同樣的哈夫曼樹進行解壓；第二遍則根據第一遍掃描得到的哈夫曼樹進行編碼，并把編碼後得到的碼字存儲起來。
哈夫曼動态編碼：動态哈夫曼編碼使用一棵動态變化的哈夫曼樹，對第t+1個字元的編碼是根據原始資料中前t個字元得到的哈夫曼樹來進行的，編碼和解碼使用相同的初始哈夫曼樹，每處理完一個字元，編碼和解碼使用相同的方法修改哈夫曼樹，是以沒有必要為解碼而儲存哈夫曼樹的資訊。編碼和解碼一個字元所需的時間與該字元的編碼長度成正比，是以動态哈夫曼編碼可實時進行。
ok,哈夫曼樹和哈夫曼編碼的知識也就這些，了解其應用價值，會簡單的構造一顆哈夫曼樹即可。