哈夫曼樹 (Huffman Tree)
導論
我們在學習哈夫曼樹之前需要先了解 什么是哈夫曼樹?
-
哈夫曼樹 是一種最優(yōu)樹,是一類帶權路徑長度最短的二叉樹,通過哈夫曼算法可以構建一棵哈夫曼樹,利用哈夫曼樹可以構造一種不等長的二進制編碼,并且構造所得的哈夫曼編碼是一種最優(yōu)前綴碼.
-
通俗來講 : n 個帶權節(jié)點均作為葉子節(jié)點,構造出的一棵帶權路徑長度最短的二叉樹,則把這棵樹稱為"哈夫曼樹" 、“赫夫曼樹” 、“Huffman Tree” 或者 “最優(yōu)二叉樹” . (備注 : 本文均用 “哈夫曼樹” 來稱呼)
第一次接觸 哈夫曼樹 的小伙伴可能對上述的定義不能第一時間消化,我們可以先來明確幾個學哈夫曼樹之前必須掌握的幾個會用到的名詞的概念,把這幾個概念理解透了之后會幫助你更好的認識哈夫曼樹.
- 路徑： 在一棵樹中 ,從一個結點到另外一個結點的通路就稱為 樹的路徑 .如圖1.1 從根節(jié)點root到D節(jié)點之間的通路就是二叉樹中的一條路徑
- 路徑長度 : 在路徑中,每經過一個結點路徑長度就加一 .如果我們規(guī)定根節(jié)點所在的樹的 層數為第一層,那么從根節(jié)點出發(fā) 走到第 i 層 ,那么當前層的節(jié)點的 路徑長度 等于 i-1,如圖1.1所示
- 樹的路徑長度 : 從根節(jié)點出發(fā)到所有結點的路徑長度之和.
- 結點的權值 : ?一個結點的權值實際上就是這個結點子樹在整個樹中所占的比例. 如圖1.1 所示 ,C、A、D、B、E結點的權分別為2、5、9、6、7.
- 結點的帶權路徑長度 : 結點到樹根之間的路徑長度與該結點權值的乘積.如圖1.1 所示 ,D結點的帶權路徑長度 = 2 * 9 = 18
- 樹的帶權路徑長度 ( Weighted Path Length of Tree 簡稱為 WPL): 樹中所有葉子結點的帶權路徑長度之和.如圖1.1 所示,該哈夫曼樹的帶權路徑長度 WPL =2 * 3 + 5 * 3 + 9 * 2 + 6 * 2 + 7 * 2 = 65
構造哈夫曼樹
要記住 哈夫曼樹 中的權值越大的結點離根節(jié)點越近,權值越小的結點離根節(jié)點越遠,這意味著一組帶權結點構造出來的哈夫曼樹中權值最小的結點離哈夫曼樹最遠,權值最大的結點離哈夫曼樹最近,也就是我們 圖1.1 中可以觀察出來的.
構造哈夫曼樹的過程其實就是"爸爸去哪兒"的過程.
語言描繪
-
形象敘述構造哈夫曼樹的步驟
從下往上構造,從已知的剩余權值集合中權值最小的那兩個結點(如果權值相同那么直接就是相同的這兩個結點),讓他們成為兄弟結點,兩兄弟的權值相加,合力找到父親結點,此時父親節(jié)點的權值就是兩兄弟結點的權值的和,然后把父親節(jié)點的權值添加到權值集合中的同時刪除這兩個兄弟節(jié)點,.重復循環(huán)"爸爸去哪兒"這個過程,直至權值集合中只剩下祖宗(根節(jié)點)為止. 那么這棵哈夫曼樹也就構造完了.
備注: 感覺核心就是你現在計劃創(chuàng)建一棵二叉樹,但是這棵二叉樹你不能隨意創(chuàng)建,而是要按照生成 “最優(yōu)二叉樹” 的規(guī)則來創(chuàng)建 ,這樣想是不是就簡單許多 ! 而這個規(guī)則就是哈夫曼算法.
-
嚴謹的構造哈夫曼樹的步驟
對于給定的有各自權值的 n 個結點
- 在 n 個權值中選出兩個最小的權值，對應的兩個結點組成一個新的二叉樹，且新二叉樹的根結點的權值為左右孩子權值的和；
- 在原有的 n 個權值中刪除那兩個最小的權值，同時將新的權值加入到 n–2 個權值的行列中，以此類推；
- 重復 1 和 2 ，直到所以的結點構建成了一棵二叉樹為止，這棵樹就是哈夫曼樹/最優(yōu)二叉樹。
注意:
- 最優(yōu)二叉樹的形態(tài)不唯一,但是WPL最小.
- 最優(yōu)二叉樹中,權越大的葉子離根越近.
圖形化理解
例如: 已知權值 W = {2,5,9,6,7},請構造哈夫曼樹.
證明結論
最優(yōu)二叉樹的形態(tài)不唯一,但是WPL最小
- 先證明第一句話: 相同的權值構造出來的哈夫曼樹形態(tài)不唯一
同樣是上述的例子,我們可以構造出另一種形態(tài)的哈夫曼樹,同時我們可以計算出兩種形態(tài)的二叉樹的帶權路徑,看看是否相等 ?
- 然后我們來證明第二句話 : 證明哈夫曼算法構造出的哈夫曼樹的WPL一定是最小的，且其他二叉樹的WPL一定大于等于哈夫曼樹的WPL。
1. 定義：
- 帶權路徑長度（WPL）是指每個葉子節(jié)點的權值乘以其深度的總和。
2. 引理：
- 對于任意的二叉樹，交換任意兩個葉子節(jié)點的位置，WPL都會增加。
3. 證明：
-
哈夫曼樹的構造過程：
- 哈夫曼算法每次選擇權值最小的兩個節(jié)點合并，構造出一顆二叉樹。
- 重復這個過程，直到所有節(jié)點合并成一個根節(jié)點，形成哈夫曼樹。
-
交換葉子節(jié)點的影響：
- 考慮哈夫曼樹的構造過程，每次選擇最小的兩個節(jié)點合并，如果我們交換了兩個葉子節(jié)點的位置，這兩個節(jié)點的權值就不再是最小的了。
- 在構造過程中，我們總是選擇權值最小的節(jié)點，因此交換葉子節(jié)點位置后，這兩個節(jié)點的合并會在構造樹的過程中晚一些，導致它們在更深的層次上，從而增加了WPL。
如果這里不懂這里的影響是什么,我會再下一篇的博客中詳細解釋,這涉及到了 貪心策略
-
結論：
- 由于哈夫曼算法保證了每次合并都選擇最小權值的節(jié)點，任何對于葉子節(jié)點位置的交換都會導致合并發(fā)生在更深的層次上，增加WPL。
- 因此，哈夫曼樹的構造方式保證了WPL最小。
4. 總結：
- 哈夫曼樹的構造方式保證了每次合并都是最優(yōu)的選擇，從而使得整個樹的WPL最小。
- 如果使用其他方式構造二叉樹，由于不能保證每次都選擇最小權值的節(jié)點進行合并，可能會導致WPL更大。
代碼實現
在構造哈夫曼樹的過程中，我們首先需要定義一個節(jié)點類來表示樹的節(jié)點，然后編寫一個構造哈夫曼樹的算法。
- 定義了一個
HuffmanNode類，用于表示哈夫曼樹的節(jié)點 - 在
HuffmanTree類中，實現一個buildHuffmanTree方法，該方法接受一個權值數組 - 使用優(yōu)先隊列來構造哈夫曼樹
- 通過
main方法演示了如何使用這個方法來構造哈夫曼樹
這個實現涉及到了優(yōu)先隊列（PriorityQueue），它是一個能夠保證每次取出的元素都是隊列中權值最小的元素的數據結構。在哈夫曼樹的構建中，我們不斷地合并權值最小的兩個節(jié)點，而優(yōu)先隊列正好能夠滿足這個需求。
package src.test.java;
import java.util.PriorityQueue;
// 定義哈夫曼樹節(jié)點類
class HuffmanNode implements Comparable<HuffmanNode> {
int weight; // 權值
HuffmanNode left; // 左子節(jié)點
HuffmanNode right; // 右子節(jié)點
public HuffmanNode(int weight) {
this.weight = weight;
}
// 實現Comparable接口，用于PriorityQueue的比較
@Override
public int compareTo(HuffmanNode other) {
return this.weight - other.weight;
}
}
public class HuffmanTree {
// 構造哈夫曼樹的方法
public static HuffmanNode buildHuffmanTree(int[] weights) {
// 使用優(yōu)先隊列來存儲節(jié)點，每次都取出權值最小的兩個節(jié)點進行合并
PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();
// 將權值數組中的每個元素轉化為節(jié)點并添加到優(yōu)先隊列中
for (int weight : weights) {
pq.add(new HuffmanNode(weight));
}
// 不斷合并節(jié)點直到只剩一個節(jié)點，即哈夫曼樹的根節(jié)點
while (pq.size() > 1) {
HuffmanNode left = pq.poll(); // 彈出權值最小的節(jié)點
HuffmanNode right = pq.poll(); // 彈出權值次小的節(jié)點
// 創(chuàng)建一個新節(jié)點，權值為兩個子節(jié)點的權值之和
HuffmanNode parent = new HuffmanNode(left.weight + right.weight);
parent.left = left;
parent.right = right;
// 將新節(jié)點添加回優(yōu)先隊列
pq.add(parent);
}
// 返回哈夫曼樹的根節(jié)點
return pq.poll();
}
// 打印哈夫曼樹的方法（可選）
public static void printHuffmanTree(HuffmanNode root, String prefix) {
if (root != null) {
System.out.println(prefix + root.weight);
printHuffmanTree(root.left, prefix + "0");
printHuffmanTree(root.right, prefix + "1");
}
}
public static void main(String[] args) {
int[] weights = {2, 5, 9, 6, 7};
// 構造哈夫曼樹
HuffmanNode root = buildHuffmanTree(weights);
// 打印哈夫曼樹（可選）
printHuffmanTree(root, "");
}
}
測試
package src.test.java;
public class HuffmanTreeTest {
public static void main(String[] args) {
int[] weights = {2, 5, 9, 6, 7};
// 構造哈夫曼樹
HuffmanNode root = HuffmanTree.buildHuffmanTree(weights);
// 打印哈夫曼樹的結構
System.out.println("Huffman Tree Structure:");
printHuffmanTreeStructure(root, "");
}
// 遞歸打印哈夫曼樹的結構
private static void printHuffmanTreeStructure(HuffmanNode root, String prefix) {
if (root != null) {
System.out.println(prefix + "Weight: " + root.weight);
if (root.left != null || root.right != null) {
System.out.println(prefix + "├── Left:");
printHuffmanTreeStructure(root.left, prefix + "│ ");
System.out.println(prefix + "└── Right:");
printHuffmanTreeStructure(root.right, prefix + " ");
}
}
}
}
結果對照
- 控制臺輸出結果
- 哈夫曼樹圖形
總結
-
基礎概念：深入了解了哈夫曼樹的概念，包括路徑、路徑長度、帶權路徑長度等基礎知識。
-
構造過程：通過圖形化和語言描述，清晰演示了從下而上構造哈夫曼樹的步驟，以及最終得到最優(yōu)二叉樹的過程。
-
證明方法：通過引理和推導，解釋了為何哈夫曼樹的構造方式能夠保證帶權路徑長度最小，涉及到了貪心策略的應用。
-
實際應用：通過Java代碼實現展示了哈夫曼樹的構造過程，將理論知識轉化為實際應用，加深了對算法的理解。文章來源：http://www.zghlxwxcb.cn/news/detail-761848.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-761848.html
到了這里，關于數據結構-構造哈夫曼樹【詳解+代碼+圖示】一文解惑！的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
