哈夫曼樹的帶權(quán)路徑長(zhǎng)度是什么？

　　1．樹的路徑長(zhǎng)度

　　樹的路徑長(zhǎng)度是從樹根到樹中每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。在結(jié)點(diǎn)數(shù)目相同的二叉樹中，完全二叉樹的路徑長(zhǎng)度最短。

　　2．樹的帶權(quán)路徑長(zhǎng)度（Weighted Path Length of Tree，簡(jiǎn)記為WPL）

　　結(jié)點(diǎn)的權(quán)：在一些應(yīng)用中，賦予樹中結(jié)點(diǎn)的一個(gè)有某種意義的實(shí)數(shù)。

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

　　樹的帶權(quán)路徑長(zhǎng)度（Weighted Path Length of Tree）：定義為樹中所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，通常記為：

　　其中：

　　n表示葉子結(jié)點(diǎn)的數(shù)目

　　wi和li分別表示葉結(jié)點(diǎn)ki的權(quán)值和根到結(jié)點(diǎn)ki之間的路徑長(zhǎng)度。

　　樹的帶權(quán)路徑長(zhǎng)度亦稱為樹的代價(jià)。

　　3．最優(yōu)二叉樹或哈夫曼樹

　　在權(quán)為wl，w2，…，wn的n個(gè)葉子所構(gòu)成的所有二叉樹中，帶權(quán)路徑長(zhǎng)度最?。创鷥r(jià)最?。┑亩鏄浞Q為最優(yōu)二叉樹或哈夫曼樹。

　　【例】給定4個(gè)葉子結(jié)點(diǎn)a，b，c和d，分別帶權(quán)7，5，2和4.構(gòu)造如下圖所示的三棵二叉樹（還有許多棵），它們的帶權(quán)路徑長(zhǎng)度分別為：

　?。╝）WPL=7*2+5*2+2*2+4*2=36

　?。╞）WPL=7*3+5*3+2*1+4*2=46

　?。╟）WPL=7*1+5*2+2*3+4*3=35

　　其中（c）樹的WPL最小，可以驗(yàn)證，它就是哈夫曼樹。

　　注意：

　?、?葉子上的權(quán)值均相同時(shí)，完全二叉樹一定是最優(yōu)二叉樹，否則完全二叉樹不一定是最優(yōu)二叉樹。

　?、?最優(yōu)二叉樹中，權(quán)越大的葉子離根越近。

　　③ 最優(yōu)二叉樹的形態(tài)不唯一，WPL最小

　　怎么求哈夫曼的帶權(quán)路徑長(zhǎng)度

　　【問(wèn)題描述】

　　已知輸入兩行正整數(shù)，第二行正整數(shù)之間用空格鍵分開，請(qǐng)建立一個(gè)哈夫曼樹，以輸入的數(shù)字為葉節(jié)點(diǎn)，求這棵哈夫曼樹的帶權(quán)路徑長(zhǎng)度。

　　【輸入形式】

　　首先第一行為輸入正整數(shù)的個(gè)數(shù)，然后接下來(lái)的一行正整數(shù)，代表葉結(jié)點(diǎn)，正整數(shù)個(gè)數(shù)不超過(guò)1000個(gè)

　　【輸出形式】

　　輸出相應(yīng)的權(quán)值

　　【樣例輸入】

　　5

　　4 5 6 7 8

　　【樣例輸出】

　　69

　　關(guān)于哈夫曼樹——

　　1、 路徑長(zhǎng)度

　　從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成兩個(gè)結(jié)點(diǎn)之間的路徑，路徑上的分支數(shù)目稱做路徑長(zhǎng)度。

　　1、 樹的路徑長(zhǎng)度

　　路徑長(zhǎng)度就是從樹根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。

　　1、 哈夫曼樹：

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

　　例： 上圖的WPL=1*5 + 2*15 + 3*40 + 4*30 + 4*10= 315

　　先了解通過(guò)剛才的步驟，我們可以得出構(gòu)造哈夫曼樹的算法描述。

　　1、根據(jù)給定的n個(gè)權(quán)值{w［1］，w［2］，…，w［n］}構(gòu)成n棵二叉樹的集合F={T［1］，T［2］，…T［n］}， 其中每棵二叉樹T［i］;中只有一個(gè)帶權(quán)為w［i］的根結(jié)點(diǎn)，其左右子樹均為空。

　　2、在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的。二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹上根結(jié)點(diǎn)的權(quán)值之和，

　　3、在F中刪除這兩棵樹，同時(shí)將新得到的二義樹加入F中。

　　4重復(fù)2和3步驟，直到F只含一棵樹為止。這棵樹便是哈夫曼樹。

　　結(jié)合例題說(shuō)明一下這個(gè)算法

　　那么可以由上面的哈夫曼樹計(jì)算出最小帶權(quán)路徑長(zhǎng)度

　　WPL = 1*9 + 2*5 + 3*2 + 4*1 + 4*2 =37

　　另外還可以有另外一個(gè)方法，結(jié)合算法描述仔細(xì)觀察發(fā)現(xiàn)最小帶權(quán)路徑長(zhǎng)度為非葉子結(jié)點(diǎn)的和 ，即

　　WPL= 19 + 10 +5 +3=37

　　至于算法的正確性，一下子也想不到什么好的辦法來(lái)證明，不過(guò)應(yīng)該是可以邏輯推導(dǎo)過(guò)來(lái)的。

　　那么要實(shí)現(xiàn)這段程序，由上面的算法描述圖我們已經(jīng)知道差不多了，主要分為三步：

　　一、排序，直到數(shù)組中只有一個(gè)數(shù)則退出

　　二、最小兩個(gè)數(shù)加起來(lái)，即為非葉子節(jié)點(diǎn)，累加到累加器中

　　三、把最小兩個(gè)數(shù)加起來(lái)作為一個(gè)新的值保存在數(shù)組中，去掉最小兩個(gè)值，跳回第一步

　　#include《stdio.h》

　　#include《stdlib.h》 //qsort（）;

　　#define N 1010

　　int rising（const void *a， const void *b）

　　{

　　return *（int*）a - *（int*）b;

　　}

　　int main（）

　　{

　　int leaf［N］ = {0}， n， i， sum = 0;

　　scanf（“%d”， &n）;

　　for（i=0; i《n; i++）

　　scanf（“%d”， leaf+i）;

　　for（i=0; i《n-1; i++）

　　{

　　qsort（leaf+i， n-i， sizeof（leaf［0］）， rising）; //排序并剔除已使用的葉結(jié)點(diǎn)

　　leaf［i+1］ += leaf［i］; //合并兩個(gè)最小的葉結(jié)點(diǎn)成一新的節(jié)點(diǎn)（放在leaf［i+1］中）

　　sum += leaf［i+1］; //總路徑長(zhǎng) = 所有非葉結(jié)點(diǎn)之和

　　}

　　printf（“%d\n”， sum）;

　　return 0;

　　}