哈夫曼樹
給定n個權值作為n個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近。
判定樹
在很多問題的處理過程中，需要進行大量的條件判斷，這些判斷結構的設計直接影響著程序的執行效率。例如，編制一個程序，將百分制轉換成五個等級輸出。大家可能認為這個程序很簡單，並且很快就可以用下列形式編寫出來：
完整代碼，以及C/C++更多學習資料，私信我“代碼“獲取
若考慮上述程序所耗費的時間，就會發現該程序的缺陷。在實際中，學生成績在五個等級上的分佈是不均勻的。當學生百分制成績的錄入量很大時，上述判定過程需要反覆調用，此時程序的執行效率將成為一個嚴重問題。
但在實際應用中，往往各個分數段的分佈並不是均勻的。下面就是在一次考試中某門課程的各分數段的分佈情況：
下面我們就利用哈夫曼樹尋找一棵最佳判定樹，即總的比較次數最少的判定樹。
- 構造方式No.1
- 構造方式No.2
這兩種方式，顯然後者的判定過程的效率要比前者高。在也沒有別地判定過程比第二種方式的效率更高。我們稱判定過程最優的二叉樹為哈夫曼樹，又稱最優二叉樹.
概念這玩意
路徑： 樹中一個結點到另一個 結點之間的分支構成這兩個結點之間的路徑。
路徑長度：路徑上的分枝數目稱作路徑長度。
樹的路徑長度：從樹根到每一個結點的路徑長度之和。
結點的帶權路徑長度：在一棵樹中，如果其結點上附帶有一個權值，通常把該結點的路徑長度與該結點上的權值之積稱為該結點的帶權路徑長度（weighted path length)。
樹的帶權路徑長度：如果樹中每個葉子上都帶有一個權值，則把樹中所有葉子的帶權路徑長度之和稱為樹的帶權路徑長度。
設某二叉樹有n個帶權值的葉子結點，則該二叉樹的帶權路徑長度記為：
公式中，Wk為第k個葉子結點的權值；Lk為該結點 的路徑長度。
樹的帶權路徑長度
其中帶權路徑長度最小的二叉樹就稱為哈夫曼樹或最優二叉樹.
哈夫曼樹的構造
根據哈弗曼樹的定義，一棵二叉樹要使其WPL值最小，必須使權值越大的葉子結點越靠近根結點，而權值越小的葉子結點越遠離根結點。
哈弗曼依據這一特點提出了一種構造最優二叉樹的方法，其基本思想如下：
下面演示了用Huffman算法構造一棵Huffman樹的過程：
哈夫曼樹的在編碼中的應用
在電文傳輸中，需要將電文中出現的每個字符進行二進制編碼。在設計編碼時需要遵守兩個原則：
（1）發送方傳輸的二進制編碼，到接收方解碼後必須具有唯一性，即解碼結果與發送方發送的電文完全一樣；
（2）發送的二進制編碼儘可能地短。下面我們介紹兩種編碼的方式。
- 等長編碼
這種編碼方式的特點是每個字符的編碼長度相同（編碼長度就是每個編碼所含的二進制位數）。假設字符集只含有4個字符A，B，C，D，用二進制兩位表示的編碼分別為00，01，10，11。若現在有一段電文為：ABACCDA，則應發送二進制序列：00010010101100，總長度為14位。當接收方接收到這段電文後，將按兩位一段進行譯碼。這種編碼的特點是譯碼簡單且具有唯一性，但編碼長度並不是最短的。
- 不等長編碼
在傳送電文時，為了使其二進制位數儘可能地少，可以將每個字符的編碼設計為不等長的，使用頻度較高的字符分配一個相對比較短的編碼，使用頻度較低的字符分配一個比較長的編碼。例如，可以為A，B，C，D四個字符分別分配0，00，1，01，並可將上述電文用二進制序列：000011010發送，其長度只有9個二進制位，但隨之帶來了一個問題，接收方接到這段電文後無法進行譯碼，因為無法斷定前面4個0是4個A，1個B、2個A，還是2個B，即譯碼不唯一，因此這種編碼方法不可使用。
因此，為了設計長短不等的編碼，以便減少電文的總長，還必須考慮編碼的唯一性，即在建立不等長編碼時必須使任何一個字符的編碼都不是另一個字符的前綴，這宗編碼稱為前綴編碼（prefix code）
通過哈夫曼樹來構造的編碼稱為哈弗曼編碼（huffman code).
- 利用字符集中每個字符的使用頻率作為權值構造一個哈夫曼樹；
- 從根結點開始，為到每個葉子結點路徑上的左分支賦予0，右分支賦予1，並從根到葉子方向形成該葉子結點的編碼
假設一個文本文件TFile中只包含7個字符{A，B，C，D，E，F，G}，這7個字符在文本中出現的次數為{5，24，7，17，34，5，13}
利用哈夫曼樹可以為文件TFile構造出符合前綴編碼要求的不等長編碼.
代碼實現
你也看花眼了就不貼出來了，需要得私信我“代碼”獲取把。
完整代碼，以及C/C++更多學習資料，私信我“代碼“獲取
編碼結果
完整代碼，以及C/C++更多學習資料，私信我“代碼“獲取
原本1個字節得東西是不是可以用二進制位去存儲啊，buffman在壓縮算法上也佔有一席之地呦。
閱讀更多 C語言源代碼計劃 的文章
