第C++使用數(shù)組來實現(xiàn)哈夫曼樹目錄寫在前面構(gòu)造思想算法設(shè)計構(gòu)造實例理解代碼確定結(jié)構(gòu)體循環(huán)找出最小值調(diào)用細(xì)節(jié)調(diào)試試圖總結(jié)

寫在前面

哈夫曼樹又稱最優(yōu)二叉樹，是一種帶權(quán)路徑長度最短的二叉樹。所謂樹的帶權(quán)路徑長度，就是樹中所有的葉結(jié)點的權(quán)值乘上其到根結(jié)點的路徑長度（若根結(jié)點為0層，葉結(jié)點到根結(jié)點的路徑長度為葉結(jié)點的層數(shù)）。樹的路徑長度是從樹根到每一結(jié)點的路徑長度之和，記為WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N個權(quán)值Wi（i=1,2,...n）構(gòu)成一棵有N個葉結(jié)點的二叉樹，相應(yīng)的葉結(jié)點的路徑長度為Li（i=1,2,...n）?？梢宰C明霍夫曼樹的WPL是最小的；但是今天，咱們不談哈夫曼編碼，就只用結(jié)構(gòu)體配合數(shù)組來完成哈夫曼樹的生成，目標(biāo)是得到正確的所有權(quán)值的和。

構(gòu)造思想

以字符的使用頻率做權(quán)構(gòu)建一棵哈夫曼樹，然后利用哈夫曼樹對字符進行編碼，俗稱哈夫曼編碼。具體來講，是將所要編碼的字符作為葉子結(jié)點，該字符在文件中的使用頻率作為葉子結(jié)點的權(quán)值，以自底向上的方式、通過執(zhí)行n-1次的合并運算后構(gòu)造出最終所要求的樹，即哈夫曼樹，它的核心思想是讓權(quán)值大的葉子離根最近。每次從樹的集合中取出雙親為0且權(quán)值最小的兩棵樹作為左、右子樹，構(gòu)造一棵新樹，新樹根結(jié)點的權(quán)值為其左右孩子結(jié)點權(quán)之和，將新樹插入到樹的集合中。

算法設(shè)計

步驟1：確定合適的數(shù)據(jù)結(jié)構(gòu)。

步驟2：初始化。構(gòu)造n棵結(jié)點為n個字符的單結(jié)點樹集合F={T1，T2,,Tn}，每棵樹中只有一個帶權(quán)的根結(jié)點，權(quán)值為該字符的使用頻率；

步驟3：如果F中只剩下一棵樹，則哈夫曼樹構(gòu)造成功，轉(zhuǎn)步驟6；否則，從集合F中取出雙親為0且權(quán)值最小的兩棵樹Ti和Tj，將它們合并成一棵新樹Zk，新樹以Ti為左兒子，Tj為右兒子（反之也可以）。新樹Zk的根結(jié)點的權(quán)值為Ti與Tj的權(quán)值之和；

步驟4：從集合F中刪去Ti、Tj，加入Zk；

步驟5：重復(fù)步驟3和4；

步驟6：從葉子結(jié)點到根結(jié)點逆向求出每個字符的哈夫曼編碼（約定左分支表示字符0，右分支表示字符1）。則從根結(jié)點到葉子結(jié)點路徑上的分支字符組成的字符串即為葉子字符的哈夫曼編碼。算法結(jié)束。

構(gòu)造實例

已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符，分別為a，b，c，d，e，f，g，h，其使用頻率分別為0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設(shè)計哈夫曼編碼。設(shè)權(quán)w=(5，29，7，8，14，23，3，11)，n=8，按哈夫曼算法的設(shè)計步驟構(gòu)造一棵哈夫曼編碼樹，具體過程如下：

理解代碼

源碼：

#includeiostream

usingnamespacestd;

#defineN8

structNode

charL;//字母

intK;//權(quán)值

boolIsRoot;//是否為根結(jié)點

intLc,Rc;//左右子樹

Node(charl='/0',intk=0,boolisRoot=false){

L=l;K=k;IsRoot=isRoot;Lc=Rc=-1;

NodeA[N+N-1]={Node('a',5,true),Node('b',29,true),Node('c',7,true),Node('d',8,true),

Node('e',14,true),Node('f',23,true),Node('g',3,true),Node('h',11,true)};

voidFindMin(NodeA[],intmin1,intmin2,intnum)

min1=num-1;

for(inti=0;inum;i++){

if(A[i].IsRootA[i].KA[min1].K)min1=i;

min2=num-1;

for(inti=0;inum;i++){

if(min1!=iA[i].IsRootA[i].KA[min2].K)min2=i;

intmain()

inty=1,num=N;

intmin1=0,min2=0;

for(inti=0;ii++){

FindMin(A,min1,min2,num);

A[num].K=A[min1].K+A[min2].K;

A[num].Lc=min1;

A[num].Rc=min2;

A[num].IsRoot=true;

A[min1].IsRoot=false;

A[min2].IsRoot=false;

A[num].L='h'+y;

y++;num++;

cout"最終權(quán)值為："A[14].Kendl;

}

確定結(jié)構(gòu)體

首先我們創(chuàng)建結(jié)點Node結(jié)構(gòu)體，并給他定義了五個屬性，分別是字符、權(quán)值、布爾型根結(jié)點標(biāo)志、以及左右子樹。隨后直接定義Node類型數(shù)組Node(charl,intk,boolisRoot)，初始化NodeA數(shù)組的長度為N+N-1的原因是：選取兩個最小權(quán)值生成新的結(jié)點，并把結(jié)點放入A數(shù)組中，相當(dāng)于每兩個結(jié)點會多生成一個節(jié)點，那么n個結(jié)點就會生成n-1個結(jié)點，總數(shù)就是n+n-1；我們依次把八個結(jié)點放入數(shù)組中，并把IsRoot置為true，初始結(jié)點均沒有參加生成新節(jié)點，都是根結(jié)點。

循環(huán)找出最小值

將A傳入找最小值的函數(shù)，初始num為N，隨著新節(jié)點的生成，逐漸++，然后默認(rèn)最小值為數(shù)組的最后一個元素，利用一重for循環(huán)遍歷出最小值和次小值，這里注意，找出的最小值必須是根結(jié)點才可以，參加過生成新結(jié)點的都要把IsRoot設(shè)為false，次小值就是在不等于最小值的情況下找出最小值。

調(diào)用細(xì)節(jié)

主函數(shù)中利用一重for循環(huán)調(diào)用FindMin函數(shù)找出兩個最小權(quán)值結(jié)點并默認(rèn)放到數(shù)組的num位置上，即為最后一個位置；首先新節(jié)點的權(quán)值由兩個最小權(quán)值相加，并把新節(jié)點的左右子樹設(shè)為找到的兩個最小權(quán)值結(jié)點，由于結(jié)構(gòu)體數(shù)組默認(rèn)IsRoot為false，所有要把新節(jié)點設(shè)為根結(jié)點，而把用過的結(jié)點取消根結(jié)點身份，L用來更換結(jié)點的字符，最后num++,y++都很好理解，經(jīng)過七次新節(jié)點的生成，我們不難猜到A[14]的權(quán)值k為100；

調(diào)試試圖

通過調(diào)試界面可以看到第一個生成的A[8]結(jié)點的左右子樹是A[0]和A[6]，而且權(quán)值正好是他們兩個結(jié)點的權(quán)相加；

A[9]的k是新的兩個最小根結(jié)點A[2]和A[8]組成的，可以確認(rèn)權(quán)值沒有問題，A[8]能參加新節(jié)點的合成說明我們成功的把他設(shè)置為了根結(jié)點，然后直接看最后一個結(jié)點的信息