哈夫曼樹的介紹

　　Huffman Tree，中文名是哈夫曼樹或霍夫曼樹，它是最優(yōu)二叉樹。

　　定義：給定n個權(quán)值作為n個葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹，若樹的帶權(quán)路徑長度達(dá)到最小，則這棵樹被稱為哈夫曼樹。 這個定義里面涉及到了幾個陌生的概念，下面就是一顆哈夫曼樹，我們來看圖解答。

　?。?） 路徑和路徑長度

　　定義：在一棵樹中，從一個結(jié)點(diǎn)往下可以達(dá)到的孩子或?qū)O子結(jié)點(diǎn)之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長度。若規(guī)定根結(jié)點(diǎn)的層數(shù)為1，則從根結(jié)點(diǎn)到第L層結(jié)點(diǎn)的路徑長度為L-1。

　　例子：100和80的路徑長度是1，50和30的路徑長度是2，20和10的路徑長度是3。

　?。?） 結(jié)點(diǎn)的權(quán)及帶權(quán)路徑長度

　　定義：若將樹中結(jié)點(diǎn)賦給一個有著某種含義的數(shù)值，則這個數(shù)值稱為該結(jié)點(diǎn)的權(quán)。結(jié)點(diǎn)的帶權(quán)路徑長度為：從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長度與該結(jié)點(diǎn)的權(quán)的乘積。

　　例子：節(jié)點(diǎn)20的路徑長度是3，它的帶權(quán)路徑長度= 路徑長度 * 權(quán) = 3 * 20 = 60。

　　（3） 樹的帶權(quán)路徑長度

　　定義：樹的帶權(quán)路徑長度規(guī)定為所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，記為WPL。

　　例子：示例中，樹的WPL= 1*100 + 2*50 + 3*20 + 3*10 = 100 + 100 + 60 + 30 = 290。

　　比較下面兩棵樹

　　上面的兩棵樹都是以{10， 20， 50， 100}為葉子節(jié)點(diǎn)的樹。

　　左邊的樹WPL=2*10 + 2*20 + 2*50 + 2*100 = 360

　　右邊的樹WPL=290

　　左邊的樹WPL 》 右邊的樹的WPL。你也可以計算除上面兩種示例之外的情況，但實(shí)際上右邊的樹就是{10，20，50，100}對應(yīng)的哈夫曼樹。至此，應(yīng)該對哈夫曼樹的概念有了一定的了解了，下面看看如何去構(gòu)造一棵哈夫曼樹。