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

（Weighted Path Length of Tree，簡(jiǎn)記為WPL）

一般的，我們是可以用常規(guī)的構(gòu)造哈夫曼樹求帶權(quán)路徑長(zhǎng)度。

計(jì)算結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：結(jié)點(diǎn)到樹根之間的路徑長(zhǎng)度與該結(jié)點(diǎn)上權(quán)的乘積。

帶權(quán)路徑長(zhǎng)度WPL（Weighted Path Length）最小的二叉樹，也稱為最優(yōu)二又樹。

在這里簡(jiǎn)單舉個(gè)例子說(shuō)一下：

題目：

給定6個(gè)字符（a,b,c,d,e,f）,它們的權(quán)值集合W =(2,3,4,7,8,9),試構(gòu)造關(guān)于W的一棵哈夫曼樹，求其帶權(quán)路徑長(zhǎng)度WPL。

解：根據(jù)題意構(gòu)造關(guān)于W的哈夫曼樹如1圖所示：

那么其帶權(quán)路徑長(zhǎng)度WPL=(9+7+8)×2+4×3+(2+3)×4=80。

（結(jié)點(diǎn)到樹根之間的路徑長(zhǎng)度與該結(jié)點(diǎn)上權(quán)的乘積）

哈夫曼樹

構(gòu)造哈夫曼樹的辦法是：在W中選出兩個(gè)權(quán)小結(jié)點(diǎn)，并同時(shí)計(jì)算出它們的和，如果兩個(gè)數(shù)的和正好是下一步的兩個(gè)最小數(shù)的其中的一個(gè)，那么這個(gè)樹直接往上生長(zhǎng)就可以了，如果這兩個(gè)數(shù)的和比較大，不是下一步的兩個(gè)最小數(shù)的其中一個(gè)，那么就并列生長(zhǎng)。

哈夫曼樹又稱最優(yōu)二叉樹，是一種帶權(quán)路徑長(zhǎng)度最短的二叉樹。所謂樹的帶權(quán)路徑長(zhǎng)度，就是樹中所有的葉結(jié)點(diǎn)的權(quán)值乘上其到根結(jié)點(diǎn)的路徑長(zhǎng)度（若根結(jié)點(diǎn)為0層，葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長(zhǎng)度為葉結(jié)點(diǎn)的層數(shù)）。樹的路徑長(zhǎng)度是從樹根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和，記為WPL=（W1L1+W2L2+W3L3+…+WnLn），N個(gè)權(quán)值Wi（i=1,2,…n）構(gòu)成一棵有N個(gè)葉結(jié)點(diǎn)的二叉樹，相應(yīng)的葉結(jié)點(diǎn)的路徑長(zhǎng)度為L(zhǎng)i（i=1,2,…n），可以證明哈夫曼樹的WPL是最小的。

總結(jié)

以上是生活随笔為你收集整理的哈夫曼树 带权路径的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。