哈夫曼樹的介紹

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

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

　　（1） 路徑和路徑長(zhǎng)度

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

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

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

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

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

　?。?） 樹的帶權(quán)路徑長(zhǎng)度

　　定義：樹的帶權(quán)路徑長(zhǎng)度規(guī)定為所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，記為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。你也可以計(jì)算除上面兩種示例之外的情況，但實(shí)際上右邊的樹就是{10，20，50，100}對(duì)應(yīng)的哈夫曼樹。至此，應(yīng)該對(duì)哈夫曼樹的概念有了一定的了解了，下面看看如何去構(gòu)造一棵哈夫曼樹。