基本概念

引子

哈夫曼樹就是尋找構造最優二叉樹，用于提高效率

基本概念

各種路徑長度

各種帶權路徑長度

結點的帶權路徑長度

樹的帶權路徑長度

哈夫曼樹

帶權路徑長度最短的樹或者二叉樹

也就是樹的葉子結點帶權路徑長度之和 ：也就是葉子結點的結點路徑長度（根結點到葉子結點的路徑數） *權重 再求和


總結：位高權重
并且哈夫曼樹不唯一

哈夫曼樹的構造

理論基礎

構造思想

可以看到 先將所有結點看成根結點構造出森林 并將權重賦值給結點
之后 選擇兩個小權重的結點 二者構造出新樹 如上圖 新樹根結點權重為子樹結點權重之和
這時要先將森林中的兩個樹刪除 之后 將兩個樹構造成的新樹加入森林（為了進行下一次權重的比較 從而下一步構造的順利進行）
重復23步 直到剩單根

度 是指結點有的子樹個數

哈夫曼樹結點的度只能是0或者2
n個葉子結點的哈夫曼樹 一共有2n-1個結點 分析如上橙色框

總結

哈夫曼樹的實現

首先是已知葉子結點的個數以及權重

依次放入結構數組的前面 數組一共長度是2n 因為結點一共有2n-1 所以構造2n的數組 不用0下標

進行第二步 合并的時候 將新合并出來的結點往后依次放入 所以根結點是數組中的最后一個位置

新節點合成的時候 要修改新節點數組中的孩子結點下標 兩個孩子要修改數組中雙親的下標

之后重復查找最小的權重的兩個結點 前提是parent值是空 這是判斷的關鍵 一旦parent值不為空的時候 就相當于退出了比較

初始化

上圖中select方法 功能是在HT[K]中選擇兩個雙親域為0并且權重最小的結點 并返回s1 s2 用于后續操作

方法參數中i-1 是新合成結點的下標 ，在選最小的兩個結點時 要從新節點前面選 這里對應理論分析中“第三步的a步驟”
i會逐漸遞增

哈夫曼編碼

前綴編碼

圖中為非前綴編碼 所以要設計任意一個字符的編碼都不是另一個字符編碼的前綴
但是可以前綴一樣 后面不一樣

哈夫曼編碼的思想

要想出現次數最多的編碼最短 正好對應哈夫曼樹的權重越大離跟結點越近的特點

所以在路徑上標注0 或者 1
看從根結點到某一個葉子結點經過的路徑 那些路徑得出來的編碼就是字符對應的二進制編碼

因為葉子結點不會出現一個字符的路徑完全包含另一個字符的路徑 所以也就是前綴編碼
并且要想出現次數最多的編碼最短 正好對應哈夫曼樹的權重越大離跟結點越近的特點 所以哈夫曼編碼效率更高

因為葉子結點不會出現一個字符的路徑完全包含另一個字符的路徑 所以也就是前綴編碼
并且要想出現次數最多的編碼最短 正好對應哈夫曼樹的權重越大離跟結點越近的特點 所以哈夫曼編碼效率更高

案例

先根據哈夫曼樹的設計思想 畫出來哈夫曼樹 在路徑上標注0 1

代碼實現

其中HC數組是指針數組 每個指針指向對應的字符串 也就是字符串的頭指針

編碼與解碼

進行哈夫曼編碼時 構造指針數組



先根據哈夫曼樹的構造思想+字符頻度表 構造出哈夫曼樹 標上各個葉子結點代表的字符 之后開始解碼 0就向左走 1就向右走 直到走到葉子結點 記錄一個字符 重復此操作即可