Huffman tree(赫夫曼樹、霍夫曼樹、哈夫曼樹、最優二叉樹)

Huffman tree(赫夫曼樹、霍夫曼樹、哈夫曼樹、最優二叉樹)

Huffman tree(赫夫曼樹、霍夫曼樹、哈夫曼樹、最優二叉樹)

flyfish 2015-8-1

Huffman tree因為翻譯不同所以有其他的名字 赫夫曼樹、霍夫曼樹、哈夫曼樹
定義引用自嚴蔚敏《數據結構》
路徑
從樹中一個結點到另一個結點之間的分支構成兩個結點之間的路徑.

路徑長度
路徑上的分支數目稱作路徑長度。

樹的路徑長度
樹的路徑長度就是從根節點到每一結點的路徑長度之和。

結點的帶權路徑長度
結點的帶權路徑長度就是從該結點到根節點之間的路徑長度與結點上權的乘積。

樹的帶權路徑長度
樹的帶權路徑長度就是樹中所有葉子結點的帶權路徑長度之和，通常記做WPL。

Huffman tree
假設有n個權值{w1,w2,…wn}，構造一棵有n個葉子結點的二叉樹，每個葉子結點帶權wi，則其中帶權路徑長度WPL最小的二叉樹稱作Huffman tree 。

假設有一個字符串每個字符出現的次數如下
A:5
B:15
C:40
D:30
E:10
將字符按照出現次數從小到大排序形成一個有序序列

自底向上建樹過程
第一步

第二步

第三步

第四步

構造完成<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPjxzdHJvbmc+uMXE7rK5s+Q8L3N0cm9uZz48L3A+DQo8cD48aW1nIGFsdD0="這裡寫圖片描述" src="http://www.bkjia.com/uploads/allimg/150803/04203L0Q-5.png" title="" />