赫夫曼樹（Huffman Tree）詳解：構造與應用

什麼是赫夫曼樹？

赫夫曼樹（Huffman Tree），又稱霍夫曼樹、哈夫曼樹或最優二叉樹，是一類帶權路徑長度（WPL）最小的二叉樹。根據嚴蔚敏《數據結構》中的定義，我們先理解幾個核心概念：

基本定義

• 路徑：樹中一個結點到另一個結點之間的分支序列。
• 路徑長度：路徑上的分支數目。
• 樹的路徑長度：從根節點到每一結點的路徑長度之和。
• 結點的帶權路徑長度：該結點到根節點的路徑長度與結點權值的乘積。
• 樹的帶權路徑長度 (WPL)：樹中所有葉子結點的帶權路徑長度之和。

赫夫曼樹的定義

給定 n 個權值 {w1, w2, ..., wn}，構造一棵擁有 n 個葉子結點的二叉樹，每個葉子結點帶權 wi。若該樹的帶權路徑長度 WPL 達到最小，則稱之為赫夫曼樹。

構造赫夫曼樹的演算法步驟

以字符出現頻率為例：A:5, B:15, C:40, D:30, E:10。將字符按頻率從小到大排序，形成有序序列。

採用自底向上的策略，重複「取出兩個最小權值節點、合併為新節點、放回序列」的過程：

第一步

合併 A(5) 和 B(15) → 新節點權值 20。

第二步

合併 E(10) 和 新節點(20) → 新節點權值 30。

第三步

合併 D(30) 和 新節點(30) → 新節點權值 60。

第四步

合併 C(40) 和 新節點(60) → 根節點權值 100，樹構造完成。

赫夫曼編碼與應用

構造完成的赫夫曼樹可為每個字符生成唯一的前綴編碼（左分支為0，右分支為1），實現無歧義的高效壓縮。例如上例中 C 頻率最高，編碼最短；A 頻率最低，編碼最長。這正是赫夫曼編碼作為經典無損壓縮演算法的核心優勢。