定義

帶權路徑長度（WPL）：設二叉樹有n個葉子結點，每個葉子結點帶有權值$w_k$，從根節點到每個葉子結點的長度為$l_k$，則每個葉子結點的帶權路徑長度之和就是：$WPL$=${\sum }_{k=1}^n$

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

哈夫曼樹的構造

每次將權值最小的兩棵二叉樹合并
如何選取兩個最小的元素？利用堆

typedef struct TreeNode *HuffmanTree; struct TreeNode{int Weight;HuffmanTree Left, Right; } HuffmanTree Huffman( MinHeap H ) { /* 假設H->Size個權值已經存在H->Elements[]->Weight里 */int i; HuffmanTree T;BuildMinHeap(H); /*將H->Elements[]按權值調整為最小堆*/for (i = 1; i < H->Size; i++) { /*做H->Size-1次合并*/T = malloc( sizeof( struct TreeNode) ); /*建立新結點*/T->Left = DeleteMin(H);/*從最小堆中刪除一個結點，作為新T的左子結點*/T->Right = DeleteMin(H);/*從最小堆中刪除一個結點，作為新T的右子結點*/T->Weight = T->Left->Weight+T->Right->Weight;/*計算新權值*/Insert( H, T ); /*將新T插入最小堆*/}T = DeleteMin(H);return T;

哈夫曼樹的特點

沒有度為1的結點

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

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

對同一組權值，是否存在不同構的兩個哈夫曼樹？ 有可能

哈夫曼編碼

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

[例]
假設有一段文本，包含58個字符，并由以下7個字符構：a，e，i，s，t，空格（sp），換行（nl）；這7個字符出現的次數不同。如何對這7個字符進行編碼，使得總編碼空間最少？

【分析】
（1）用等長ASCII編碼：58 ×8 = 464位；
（2）用等長3位編碼：58 ×3 = 174位；
（3）不等長編碼：出現頻率高的字符用的編碼短些，出現頻率低的字符則可以編碼長些？

怎么進行不等長編碼？ 如何避免二義性？

前綴碼prefix code：任何字符的編碼都不是另一字符編碼的前綴
可以無二義地解碼

怎么構造一顆編碼代價最小的二叉樹？

代價最小且不會有二義性

參考資料

浙大數據結構MOOC

總結

以上是生活随笔為你收集整理的【数据结构】哈夫曼树与哈夫曼编码的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。