求哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度

1、求哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)題目描述：weight,題目需要輸出所有哈夫曼樹(shù)，第一行輸入一個(gè)數(shù) n，表示葉結(jié)點(diǎn)的個(gè)數(shù)。需要用這些葉結(jié)點(diǎn)生成哈夫曼樹(shù)，根據(jù)哈夫曼樹(shù)的概念，這些結(jié)點(diǎn)有權(quán)值，即結(jié)點(diǎn)的值與權(quán)值的乘積之和。輸入：輸入有多組數(shù)據(jù)。每組第一行輸入一個(gè)數(shù)n，接著輸入n個(gè)葉節(jié)點(diǎn)（葉節(jié)點(diǎn)權(quán)值不超過(guò) 100， 2<=n<=1000 ）。輸出：輸出權(quán)值。樣例輸入：51 2 2 5 9樣例輸出：37來(lái)源：2010年北京郵電大學(xué)計(jì)算機(jī)研究生機(jī)試真題，都很少有構(gòu)造最優(yōu)二叉樹(shù)（也題目解析：由于這是一道機(jī)試題目，不可能讓你在短短的時(shí)間內(nèi)構(gòu)造一顆二叉樹(shù)然后再求解，而且查閱一般的資料（算法導(dǎo)論等）即是哈夫曼樹(shù)

2、）的方法。因此只能根據(jù)構(gòu)造哈夫曼樹(shù)的原理來(lái)計(jì)算這個(gè)帶權(quán)路徑長(zhǎng)度值。首先，有必要了解一下哈夫曼樹(shù)的一些基本概念：1、路徑長(zhǎng)度從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成兩個(gè)結(jié)點(diǎn)之間的路徑，路徑上的分支數(shù)目稱做路徑長(zhǎng)度。分支圖1從根節(jié)點(diǎn)到D節(jié)點(diǎn)的路徑長(zhǎng)度為41、樹(shù)的路徑長(zhǎng)度路徑長(zhǎng)度就是從樹(shù)根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和圖2樹(shù)的路徑長(zhǎng)度為1 + 1+2+2+3+3+4+4=201、哈夫曼樹(shù)：帶權(quán)路徑長(zhǎng)度 WPL (Weighted Path Length )最小的二叉樹(shù)，也稱為最優(yōu)二又樹(shù).例:上圖的 WPL=1*5 + 2*15 + 3*40 + 4*30 + 4*10= 315先了解通過(guò)剛才的步驟，我們可

3、以得出構(gòu)造哈夫曼樹(shù)的算法描述。1、 根據(jù)給定的n個(gè)權(quán)值w1,w2,wn構(gòu)成n棵二叉樹(shù)的集合F=T1,T2,Tn其中每棵二叉樹(shù)Ti;中只有一個(gè)帶權(quán)為 wi的根結(jié)點(diǎn)，其左右子樹(shù)均為空。2、 在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為左右子樹(shù)構(gòu)造一棵新的.二叉樹(shù)，且置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和，3、在F中刪除這兩棵樹(shù)，同時(shí)將新得到的二義樹(shù)加入F中。4重復(fù)2和3步驟，直到F只含一棵樹(shù)為止。這棵樹(shù)便是哈夫曼樹(shù)結(jié)合例題說(shuō)明一下這個(gè)算法圖3哈夫曼樹(shù)的構(gòu)造過(guò)程示意圖圖4最終結(jié)果那么可以由上面的哈夫曼樹(shù)計(jì)算出最小帶權(quán)路徑長(zhǎng)度WPL = 1*9 + 2*5 + 3*2 + 4*1 + 4*

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è)值，跳回第一步cpp view plain copy1.#in clude<stdio.h>2.#in clude<stdlib.h>3.

5、int cmp( const void *a, const void *b)4.5.return *( int *)a-*( int *)b;6.7.int main( void )8.9.int n,W1001;10.while (scanf("%d"，&n)!=EOF)11.12.for (int i=1;i<二n;i+)13.scanf("%d"，&Wi);14.int Result=0;15.for (int i=2;i<二n;i+)16.17.qsort(W+i-1, n-i+2,sizeof (W0),cmp);18.Result+