哈夫曼樹的構(gòu)造

　　根據(jù)哈弗曼樹的定義，一棵二叉樹要使其WPL值最小，必須使權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。

　　哈弗曼依據(jù)這一特點(diǎn)提出了一種構(gòu)造最優(yōu)二叉樹的方法，其基本思想如下：

　　下面演示了用Huffman算法構(gòu)造一棵Huffman樹的過程：

　　假設(shè)有n個(gè)權(quán)值，則構(gòu)造出的哈夫曼樹有n個(gè)葉子結(jié)點(diǎn)。 n個(gè)權(quán)值分別設(shè)為 w1、w2、…、wn，則哈夫曼樹的構(gòu)造規(guī)則為：

　　（1） 將w1、w2、…，wn看成是有n 棵樹的森林（每棵樹僅有一個(gè)結(jié)點(diǎn)）；

　　（2） 在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結(jié)點(diǎn)權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和；

　　（3）從森林中刪除選取的兩棵樹，并將新樹加入森林；

　?。?）重復(fù)（2）、（3）步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。

　　如：對(duì) 下圖中的六個(gè)帶權(quán)葉子結(jié)點(diǎn)來構(gòu)造一棵哈夫曼樹，步驟如下：

　　注意：為了使得到的哈夫曼樹的結(jié)構(gòu)盡量唯一，通常規(guī)定生成的哈夫曼樹中每個(gè)結(jié)點(diǎn)的左子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)點(diǎn)的權(quán)。

　　具體算法如下：

　　//2、根據(jù)數(shù)組 a 中 n 個(gè)權(quán)值建立一棵哈夫曼樹，返回樹根指針

　　struct BTreeNode* CreateHuffman（ElemType a［］， int n）

　　{

　　int i， j;

　　struct BTreeNode **b， *q;

　　b = malloc（n*sizeof（struct BTreeNode））;

　　for （i = 0; i 《 n; i++） //初始化b指針數(shù)組，使每個(gè)指針元素指向a數(shù)組中對(duì)應(yīng)的元素結(jié)點(diǎn)

　　{

　　b［i］ = malloc（sizeof（struct BTreeNode））;

　　b［i］-》data = a［i］;

　　b［i］-》left = b［i］-》right = NULL;

　　}

　　for （i = 1; i 《 n; i++）//進(jìn)行 n-1 次循環(huán)建立哈夫曼樹

　　{

　　//k1表示森林中具有最小權(quán)值的樹根結(jié)點(diǎn)的下標(biāo)，k2為次最小的下標(biāo)

　　int k1 = -1， k2;

　　for （j = 0; j 《 n; j++）//讓k1初始指向森林中第一棵樹，k2指向第二棵

　　{

　　if （b［j］ ！= NULL && k1 == -1）

　　{

　　k1 = j;

　　continue;

　　}

　　if （b［j］ ！= NULL）

　　{

　　k2 = j;

　　break;

　　}

　　}

　　for （j = k2; j 《 n; j++）//從當(dāng)前森林中求出最小權(quán)值樹和次最小

　　{

　　if （b［j］ ！= NULL）

　　{

　　if （b［j］-》data 《 b［k1］-》data）

　　{

　　k2 = k1;

　　k1 = j;

　　}

　　else if （b［j］-》data 《 b［k2］-》data）

　　k2 = j;

　　}

　　}

　　//由最小權(quán)值樹和次最小權(quán)值樹建立一棵新樹，q指向樹根結(jié)點(diǎn)

　　q = malloc（sizeof（struct BTreeNode））;

　　q-》data = b［k1］-》data + b［k2］-》data;

　　q-》left = b［k1］;

　　q-》right = b［k2］;

　　b［k1］ = q;//將指向新樹的指針賦給b指針數(shù)組中k1位置

　　b［k2］ = NULL;//k2位置為空

　　}

　　free（b）; //刪除動(dòng)態(tài)建立的數(shù)組b

　　return q; //返回整個(gè)哈夫曼樹的樹根指針

　　}