哈夫曼樹和哈夫曼編碼（檔案壓縮）

哈夫曼樹（Huffman Tree)

帶權路徑長度（WPL）:設二叉樹有n個葉子結點，每個葉子結點帶有權值Wk,從根節點到每個葉子結點的長度為Lk,則每個葉子結點帶權路徑長度之和就是(wk* Lk)求和

最優二叉樹或哈夫曼樹：WPL最小的二叉樹

哈夫曼樹的構造：每次把權值最小的兩棵二叉樹合并

1 HuffmanTree Huffman(MinHeap H)
 2 {
 3     //這裡最小堆的元素類型為HuffmanTree，排序的原則是結點的權值資料
 4     //假設H->Size個權值已經存在在H->Data[]->weight裡
 5     int i, N;
 6     HuffmanTree T;
 7 
 8     BuildMinHeap(H);        //根據結點的權值将H調整為最小堆
 9     N = H->Size;
10     for (i = 1; i < N; i++)        //做H->Size - 1次合并
11     {
12         T = (HuffmanTree)malloc(sizeof(struct HTNode));        //建立一個新的哈夫曼結點
13         T->Left = DeleteMin(H);        //将最小堆中的最小元素，即根節點删除後傳回，作為這個哈夫曼結點的左子結點
14         T->Right = DeleteMin(H);        //再次将最小堆中的根節點删除後傳回，作為這個哈夫曼樹的右子結點
15         //哈夫曼節點的權值等于左右子節點的權值之和
16         T->weight = T->Left->weight + T->Right->weight;
17         Insert(H, T);
18     }
19 
20     return DeleteMin(H);    //最小堆中最後一個元素即使指向哈夫曼樹根節點的指針
21 }      

哈夫曼樹的特點：

沒有度為1的結點

n個葉子結點的哈夫曼樹共有2n-1個結點

哈夫曼樹的任意非葉結點的左右子樹交換後仍是哈夫曼樹

對同一組權值，存在不同構的兩棵哈夫曼樹，但兩棵樹的WPL相等

哈夫曼編碼（檔案壓縮）：

給定一段字元串，如何對字元進行編碼，可以使得該字元串的編碼存儲空間最少

字首碼：（prefix code)任何字元的編碼都不是另一字元編碼的字首，可避免二義性

二叉樹表示法：每個字元通過從根節點開始用0訓示左分支，用1訓示右分支而已記錄路徑的方法表示出來

用二叉樹進行編碼：

（1）左右分支：0、 1

（2）字元隻在葉結點上

用哈夫曼樹的規則構造這棵二叉樹