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

《求哈夫曼樹的帶權(quán)路徑長(zhǎng)度》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

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

2、即是哈夫曼樹)的方法。因此只能根據(jù)構(gòu)造哈夫曼樹的原理來計(jì)算這個(gè)帶權(quán)路徑長(zhǎng)度值。首先，有必要了解一下哈夫曼樹的一些基本概念:1、路徑長(zhǎng)度從樹中一個(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、樹的路徑長(zhǎng)度路徑長(zhǎng)度就是從樹根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。圖2樹的路徑長(zhǎng)度為1+1+2+2+3+3+4+4=201、哈夫曼樹:帶權(quán)路徑長(zhǎng)度WPL（WeightedPathLength）最小的二叉樹，也稱為最優(yōu)二又樹.例:上圖的WPL=1*5+2*15+3*40+4*30+4*10=315?先了解通過

3、剛才的步驟，我們可以得出構(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é)合例題說明一下這個(gè)算法圖3哈夫曼樹的構(gòu)造過程示意圖圖4最終結(jié)果那么可

4、以由上面的哈夫曼樹計(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至于算法的正確性，一下子也想不到什么好的辦法來證明，不過應(yīng)該是可以邏輯推導(dǎo)過來的。那么要實(shí)現(xiàn)這段程序，由上面的算法描述圖我們已經(jīng)知道差不多了，主要分為三步：一、排序,直到數(shù)組中只有一個(gè)數(shù)則退出二、最小兩個(gè)數(shù)加起來，即為非葉子節(jié)點(diǎn)，累加到累加器中三、把最小兩個(gè)數(shù)加起來作為一個(gè)新的值保存在數(shù)組中，去掉最小兩個(gè)值，跳回第一步[cpp]?viewplain

5、?copy1.#include??2.#include??3.int?cmp(const?void?*a,const?void?*b)??4.{??5.????return?*(int?*)a-*(int?*)b;??6.}??7.int?main(void)??8.{??9.????int?n,W[1001];??10.????while(scanf("%d",&n)!=EOF)??11.????{??12.????????for(int?i=1;i<=n;i++)??13.????????????scanf("%d

6、",&W[i]);??14.????????int?Result=0;??15.????????for(int?i=2;i<=n;i++)??16.????????{??17.????????????qsort(W+i-1,n-i+2,sizeof(W[0]),cmp);??18.????????????Result+=W[i]+W[i-1];??19.????????????W[i]=W[i]+W[i-1];??20.????????}??21.????????printf("%d",Result);??22.????}??23.????return

7、?0;??24.}