數(shù)據(jù)結(jié)構(gòu)—基礎(chǔ)知識(shí)：哈夫曼樹(shù)

哈夫曼樹(shù)的基本概念

哈夫曼（Huffman）樹(shù)又稱最優(yōu)樹(shù)，是一類帶權(quán)路徑長(zhǎng)度最短的樹(shù)，在實(shí)際中有廣泛的用途。哈夫曼樹(shù)的定義，涉及路徑、路徑長(zhǎng)度、權(quán)等概念，下面先給出這些概念的定義，然后再介紹哈夫曼樹(shù)

1. 路徑：從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。
2. 路徑長(zhǎng)度：路徑上的分支數(shù)目稱作路徑長(zhǎng)度。
3. 樹(shù)的路徑長(zhǎng)度：從樹(shù)根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。
4. 權(quán)：賦予某個(gè)實(shí)體的一個(gè)量，是對(duì)實(shí)體的某個(gè)或某些屬性的數(shù)值化描述。在數(shù)據(jù)結(jié)構(gòu)中，實(shí)體有結(jié)點(diǎn)（元素）和邊（關(guān)系）兩大類，所以對(duì)應(yīng)有結(jié)點(diǎn)權(quán)利邊權(quán)結(jié)點(diǎn)權(quán)或邊權(quán)具體代表什么意義，由具體情況決定。如果在一棵樹(shù)中的結(jié)點(diǎn)上帶有權(quán)值，則對(duì)應(yīng)的就有帶權(quán)樹(shù)等概念。
5. 結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：從該結(jié)點(diǎn)到樹(shù)根之間的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積。
6. 樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，通常記作WPL。
7. 哈夫曼樹(shù)：設(shè)有m個(gè)權(quán)值{w1，w2，…wm},可以構(gòu)造一棵含n個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)，每個(gè)葉子結(jié)點(diǎn)的權(quán)為w，則其中帶權(quán)路徑長(zhǎng)度WPL最小的一叉樹(shù)稱做最優(yōu)二叉樹(shù)或哈夫曼樹(shù)。

例如，下圖中所示的3棵二叉樹(shù)，都含4個(gè)葉子結(jié)點(diǎn)a、b、c、d，分別帶權(quán)7、5、2、4，他們的帶權(quán)路徑長(zhǎng)度分別為

哈夫曼樹(shù)的構(gòu)造算法

哈夫曼樹(shù)的構(gòu)造過(guò)程

1. 根據(jù)給定的n個(gè)權(quán)值{w1，w?，…，wn}，構(gòu)造n棵只有根結(jié)點(diǎn)的二叉樹(shù)，這n棵二叉樹(shù)構(gòu)成一個(gè)森林F。
2. 在森林F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，且置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和。（選用兩小造新樹(shù)）
3. 在森林F中刪除這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加人F中。（刪除兩小添新人）
4. 重復(fù)(2)和(3),直到F只含一棵樹(shù)為止。這棵樹(shù)便是哈夫曼樹(shù)。（重復(fù)(2)(3)剩單根）

在構(gòu)造哈夫曼樹(shù)時(shí)，首先選擇權(quán)小的，這樣保證權(quán)大的離根較近，這樣一來(lái)，在計(jì)算樹(shù)的帶權(quán)路徑長(zhǎng)度時(shí)，自然會(huì)得到最小帶權(quán)路徑長(zhǎng)度，這種生成算法是一種典型的貪心法。

注：哈夫曼樹(shù)的結(jié)點(diǎn)的度數(shù)為0或2，沒(méi)有度為1的結(jié)點(diǎn)。

哈夫曼算法的實(shí)現(xiàn)

//-------哈夫曼樹(shù)的存儲(chǔ)表示-------
typedef struct{int weight;//結(jié)點(diǎn)的權(quán)值int parent,lchild,rchild;//結(jié)點(diǎn)的雙親、左孩子、右孩子的下標(biāo)
}HTNode,*HuffmanTree;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹(shù)

權(quán)值	雙親	左孩子	右孩子
weight	parent	lchild	rchild

包含n棵樹(shù)的森林經(jīng)過(guò)n-1次合并才能形成哈夫曼樹(shù)，共產(chǎn)生n-1個(gè)新結(jié)點(diǎn)

算法：構(gòu)造哈夫曼樹(shù)

【算法步驟】

1. 初始化：首先動(dòng)態(tài)申請(qǐng)2n個(gè)單元;然后循環(huán) 2n-1次，從1號(hào)單元開(kāi)始，依次將1至2n-1所有單元中的雙親、左孩子、右孩子的下標(biāo)都初始化為0；最后再循環(huán)n次，輸入前n個(gè)單元中葉子結(jié)點(diǎn)的權(quán)值。
2. 創(chuàng)建樹(shù):循環(huán)n-1次，通過(guò)n-1次的選擇、刪除與合并來(lái)創(chuàng)建哈夫曼樹(shù)。選擇是從當(dāng)前森林中選擇雙親為0且權(quán)值最小的兩個(gè)樹(shù)根結(jié)點(diǎn)s1和 s2；刪除是指將結(jié)點(diǎn)s1 和s2白的雙親改為非 0；合并就是將s1 和 s2的權(quán)值和作為一個(gè)新結(jié)點(diǎn)的權(quán)值依次存入到數(shù)組的第n+1之后的單元中，同時(shí)記錄這個(gè)新結(jié)點(diǎn)左孩子的下標(biāo)為s1，右孩子的下標(biāo)為 s2。

void CreateHuffmanTree(HuffmanTree &HT,int n)
{if(n<=1) return;m=2*n-1;HT=new HTNode[m+1];//0號(hào)單元未用，所以需要?jiǎng)討B(tài)分配m+1個(gè)單元，HT[m]表示根結(jié)點(diǎn)for(i=1;i<=m,++1)//將1~m號(hào)單元中的雙親、左孩子，右孩子的下標(biāo)都初始化為0{HT[i].parnt=0;HT[i].lchild=0;HT[i].rchild=0;}for(i=1;i<=n,++1)//輸入前n個(gè)單元中葉子結(jié)點(diǎn)的權(quán)值cin>>HT[i].weight;
/*-----------初始化工作結(jié)束，下面開(kāi)始創(chuàng)建哈夫曼樹(shù)-----------*/for(i=n+1;i<=n;++1){//通過(guò)n-1次的選擇、刪除、合并來(lái)創(chuàng)建哈夫曼樹(shù)Select(HT,i-1,s1,s2);//在HT[k]（1≤k≤i-1）中選擇兩個(gè)其雙親域0且權(quán)值最小的結(jié)點(diǎn)，并返回它們?cè)贖T中的序號(hào)s1和s2（最小結(jié)點(diǎn)下標(biāo)）HT[s1].parent=i;HT[s2].parent=i;//修改HT[s1][s2]的parent值HT[i].lchild=s1;HT[i].rchild=s2;//s1,s2分別作為i的左右孩子HT[i].weight=HT[s1].weight+HT[s2].weight;//i的權(quán)值為左右孩子之和}
}

已知w=（5，29，7，8，14，23，3，11），構(gòu)造一棵哈夫曼樹(shù)，計(jì)算樹(shù)的帶權(quán)路徑長(zhǎng)度，并給出構(gòu)造過(guò)程中存儲(chǔ)結(jié)構(gòu)HT的初始狀態(tài)和終結(jié)狀態(tài)。

HT初態(tài)
結(jié)點(diǎn)i	weight	parent	lchild	rchild
1	5	0	0	0
2	29	0	0	0
3	7	0	0	0
4	8	0	0	0
5	14	0	0	0
6	23	0	0	0
7	3	0	0	0
8	11	0	0	0
9	-	0	0	0
10	-	0	0	0
11	-	0	0	0
12	-	0	0	0
13	-	0	0	0
14	-	0	0	0
15	-	0	0	0

HT的終態(tài)
結(jié)點(diǎn)i	weight	parent	lchild	rchild
1	5	9	0	0
2	29	14	0	0
3	7	10	0	0
4	8	10	0	0
5	14	12	0	0
6	23	13	0	0
7	3	9	0	0
8	11	11	0	0
9	8	11	7	1
10	15	12	3	4
11	19	13	9	8
12	29	14	5	10
13	42	15	11	6
14	58	15	2	12
15	100	0	13	14

?