基本術語

   　哈夫曼樹又稱為最優(yōu)樹.

　　1、路徑和路徑長度

　　在一棵樹中，從一個結點往下可以達到的孩子或子孫結點之間的通路，稱為路徑。

　　通路中分支的數(shù)目稱為路徑長度。若規(guī)定根結點的層數(shù)為1，

　　則從根結點到第L層結點的路徑長度為L-1。

　　2、結點的權及帶權路徑長度

　　若將樹中結點賦給一個有著某種含義的數(shù)值，則這個數(shù)值稱為該結點的權。

　　結點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積。

　　3、樹的帶權路徑長度

　　樹的帶權路徑長度規(guī)定為所有葉子結點的帶權路徑長度之和，記為WPL。

Huffman的構造方法

　　假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。

　　n個權值分別設為 w1、w2、…、wn，則哈夫曼樹的構造規(guī)則為：

　　(1) 將w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結點)；

　　(2) 在森林中選出兩個根結點的權值最小的樹合并，

　　作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；

　　(3)從森林中刪除選取的兩棵樹，并將新樹加入森林；

　　(4)重復(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。