1.概念
哈夫曼樹（Huffman Tree）是一種用于數據壓縮的二叉樹，由大衛·哈夫曼（David A. Huffman）于1952年提出。它通過構建最優二叉樹來實現數據的高效壓縮，廣泛應用于文件壓縮、圖像壓縮等領域。
哈夫曼樹的核心思想
哈夫曼樹的核心思想是用較短的編碼表示出現頻率較高的字符，用較長的編碼表示出現頻率較低的字符，從而減少整體的編碼長度。
2.構建哈夫曼樹的步驟
-
統計字符頻率：
-
統計待壓縮數據中每個字符出現的頻率。
-
-
創建節點：
-
為每個字符創建一個節點，節點的權重為字符的頻率。
-
-
構建優先隊列：
-
將所有節點放入一個優先隊列（最小堆），按權重從小到大排序。
-
-
合并節點：
-
從優先隊列中取出權重最小的兩個節點，合并成一個新節點，新節點的權重為這兩個節點的權重之和。
-
將新節點放回優先隊列。
-
-
重復合并：
-
重復上述步驟，直到優先隊列中只剩一個節點，這個節點就是哈夫曼樹的根節點。
-
-
生成編碼：
-
從根節點開始，向左子樹走標記為0，向右子樹走標記為1，直到葉子節點，得到每個字符的哈夫曼編碼。
-
3.哈夫曼樹的特點
-
最優前綴編碼：哈夫曼編碼是一種前綴編碼，沒有任何一個編碼是另一個編碼的前綴。
-
最小加權路徑長度：哈夫曼樹的帶權路徑長度（WPL）最小，即壓縮效率最高。
示例
假設有以下字符及其頻率：
-
A: 5
-
B: 9
-
C: 12
-
D: 13
-
E: 16
-
F: 45
構建哈夫曼樹的過程：
-
將所有字符節點放入優先隊列。
-
取出A(5)和B(9)，合并為新節點(14)，放回隊列。
-
取出C(12)和D(13)，合并為新節點(25)，放回隊列。
-
取出E(16)和新節點(14)，合并為新節點(30)，放回隊列。
-
取出新節點(25)和F(45)，合并為新節點(70)，放回隊列。
-
取出新節點(30)和新節點(70)，合并為根節點(100)。
根據哈夫曼樹的構建規則和正確的路徑長度過程：
(100)/ \(30) (70)/ \ / \
(14) E(16) (25) F(45)/ \ / \
A(5) B(9) C(12) D(13)? 路徑長度：
-
A：根 → 30 → 14 → A，路徑長度?3。
-
B：根 → 30 → 14 → B，路徑長度?3。
-
C：根 → 70 → 25 → C，路徑長度 3。
-
D：根 → 70 → 25 → D，路徑長度 3。
-
E：根 → 30 → E，路徑長度?2。
-
F：根 → 70 → F，路徑長度?2。
計算 WPL
| 字符 | 權重（頻率） | 路徑長度 | 權重 × 路徑長度 |
|---|---|---|---|
| A | 5 | 3 | 5×3=15 |
| B | 9 | 3 | 9×3=27 |
| C | 12 | 3 | 12×3=36 |
| D | 13 | 3 | 13×3=39 |
| E | 16 | 2 | 16×2=32 |
| F | 45 | 2 | 45×2=90 |
WPL 總和：
15+27+36+39+32+90=239
總結
路徑長度是哈夫曼樹中一個重要的概念，它直接決定了每個字符的編碼長度。通過最小化帶權路徑長度（WPL），哈夫曼樹能夠實現數據的高效壓縮。
)
