408答疑

---

---

三、樹與二叉樹的應用

哈夫曼樹和哈夫曼編碼

哈夫曼樹的定義

概念

• 哈夫曼樹是帶權路徑長度（WPL）?最小的二叉樹，又稱最優二叉樹。
• ?權值：樹中結點被賦予的表示特定意義的數值。
• ?葉結點的帶權路徑長度：葉結點到根結點的路徑長度與該結點權值的乘積。
• ?樹的帶權路徑長度（WPL）?：樹中所有葉結點的帶權路徑長度之和，計算公式為：
  $$WPL=\sum _{i=1}^n{w}_i{l}_i$$
  其中，$w_i$ 為第 $i$ 個葉結點的權值，$l_i$ 為該葉結點到根結點的路徑長度。

帶權路徑長度（WPL）計算

• 目標：構造 WPL 最小的二叉樹（哈夫曼樹）。
• ?路徑長度：從根到某結點的路徑上的邊數（層數減1）。

示例分析

以下為三棵含4個葉結點（權值分別為7, 5, 2, 4）的二叉樹及其 WPL 計算：

• ?二叉樹(1)

  • 葉結點路徑長度均為2
  • $WPL=7\times 2+5\times 2+2\times 2+4\times 2=36$

• ?二叉樹(2)

  • 葉結點路徑長度分別為2, 3, 3, 1
  • $WPL=4\times 2+7\times 3+5\times 3+2\times 1=46$

• ?二叉樹(3)（哈夫曼樹）

  • 葉結點路徑長度分別為1, 2, 3, 3
  • $WPL=7\times 1+5\times 2+2\times 3+4\times 3=35$

結論：二叉樹(3)的 WPL 最小，符合哈夫曼樹的定義。

哈夫曼樹的構造

算法描述

給定 $n$ 個權值分別為 $w_1,w_2,\dots ,w_n$ 的結點，構造Huffman樹的算法描述如下：

1. 將這 $n$ 個結點分別作為 $n$ 棵僅含一個結點的二叉樹，構成森林 $F$。
2. 構造一個新結點，從 $F$ 中選取兩棵根結點權值最小的樹作為新結點的左、右子樹，并且將新結點的權值置為左、右子樹上根結點的權值之和。
3. 從 $F$ 中刪除剛才選出的兩棵樹，同時將新得到的樹加入 $F$ 中。
4. 重復步驟 2 和 3，直至 $F$ 中只剩下一棵樹為止。

哈夫曼樹的性質

從上述構造過程中可以看出哈夫曼樹具有如下特點：

1. 每個初始結點最終都成為葉結點，且權值越小的結點到根結點的路徑長度越大。
2. 構造過程中共新建了 $n?1$ 個結點（雙分支結點），因此哈夫曼樹的結點總數為 $2n?1$。
3. 每次構造都選擇 2 棵樹作為新結點的孩子，因此哈夫曼樹中不存在度為 1 的結點。

示例

例如，權值 { 7 , 5 , 2 , 4 } \{7, 5, 2, 4\} {7,5,2,4} 的哈夫曼樹的構造過程如下圖所示：

• (1) 初始狀態，權值分別為 7, 5, 2, 4。
• (2) 第一次合并，將權值 2 和 4 的結點合并，新結點權值為 6。
• (3) 第二次合并，將權值 5 和 6 的結點合并，新結點權值為 11。
• (4) 最終態，最終哈夫曼樹的權值為 18。

通過這個過程，可以驗證下圖(4)樹的帶權路徑長度 (WPL) 最小，因此它恰好為哈夫曼樹。

哈夫曼編碼

Huffman樹的編碼規則

• Huffman樹的左樹編碼為0，右樹編碼為1，則每一個葉子結點將得到唯一的編碼，即為Huffman編碼。

Huffman樹的構建過程

1. 先以字符串中每個字符出現的次數為權值構建Huffman樹。
2. 從根結點開始對分支進行編碼，左分支為0，右分支為1。
3. 所有權值結點都在葉子結點位置，遍歷從根到葉子結點的每條路徑，將獲得對應字符的Huffman編碼。

前綴編碼

• 若沒有一個編碼是另一個編碼的前綴，則稱這樣的編碼為前綴編碼。
• 對前綴編碼的解碼很簡單，因為沒有一個編碼是其他編碼的前綴。所以識別出第一個編碼，將它翻譯為原字符，再對剩余的碼串執行同樣的解碼操作。
• 例如，碼串 0010110 可被唯一地翻譯為 A, A, B 和 C。另舉反例：若再將字符 D 的編碼設計為 11，此時 11 是 110 的前綴，則上述碼串的后三位就無法唯一翻譯。

前綴編碼的分析及應用

• Huffman編碼可以利用二叉樹來設計二進制前綴編碼。假設為 A, B, C, D 四個字符設計前綴編碼，可以用下圖所示的二叉樹來表示，4 個葉結點分別表示 4 個字符，且約定左分支表示 0，右分支表示 1，從根到葉結點的路徑上用分支標記組成的序列作為該葉結點字符的編碼，可以證明如此得到的必為前綴編碼。由下圖得到字符 A, B, C, D 的前綴編碼分別為 0, 10, 110, 111。

Huffman樹的構造及相關的分析

壓縮原理

• 在未壓縮之前一個字符占一個字節，現在對字符進行二進制編碼之后，一個字節8個比特位列現在可以表示多個字符，所以說一次壓縮，就會節省很多字節，也就起到了壓縮的作用。
• Huffman編碼是一種非常有效的數據壓縮編碼。由Huffman樹得到Huffman編碼是很自然的過程。首先，將每個字符當作一個獨立的結點，其權值為它出現的頻度（或次數），構造出對應的Huffman樹。然后，將從根到葉結點的路徑上分支標記的字符串作為該字符的編碼。

示例分析

• 例如，下圖所示為一個由Huffman樹構造Huffman編碼的示例，矩形方塊表示字符及其出現的次數。這棵哈夫曼樹的 WPL 為 $WPL=1\times 45+3\times (13+12+16)+4\times (5+9)=224$。此處的 WPL 可視為最終編碼得到二進制編碼的長度，共 224 位。若采用 3 位固定長度編碼，則得到的二進制編碼長度為 300 位，因此 Huffman編碼共壓縮了 25% 的數據。利用 Huffman樹可以設計出總長度最短的二進制前綴編碼。

注意事項

• 左分支和右分支究竟是表示 0 還是表示 1 沒有明確規定，因此構造出的哈夫曼樹并不唯一，但各哈夫曼樹的帶權路徑長度 WPL 相同且為最優。此外，如有若干權值相同的結點，則構造出的哈夫曼樹更可能不同，但 WPL 必然相同且為最優。

并查集（略）

四、參考資料

鮑魚科技課件

b站免費王道課后題講解:

網課全程班:

26王道考研書