寫(xiě)在前面

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

構(gòu)造思想

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

算法設(shè)計(jì)

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

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

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

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

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

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

構(gòu)造實(shí)例

已知某系統(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è)計(jì)哈夫曼編碼。設(shè)權(quán)w=(5，29，7，8，14，23，3，11)，n=8，按哈夫曼算法的設(shè)計(jì)步驟構(gòu)造一棵哈夫曼編碼樹(shù)，具體過(guò)程如下：

理解代碼

源碼：

#include <iostream>
using namespace std;
#define N 8
struct Node 
{
	char L;//字母
	int K;//權(quán)值
	bool IsRoot;//是否為根結(jié)點(diǎn)
	int Lc, Rc;//左右子樹(shù)
	Node(char l = '/0', int k = 0, bool isRoot = false) {
		L = l; K = k; IsRoot = isRoot; Lc = Rc = -1;
	}
};
Node A[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) };
void FindMin(Node A[], int &min1, int &min2,int num)
{
	min1 = num - 1;
	for (int i = 0; i < num; i++) {
		if (A[i].IsRoot && A[i].K < A[min1].K) min1 = i;
	}
	min2 = num - 1;
	for (int i = 0; i < num; i++) {
		if (min1 != i && A[i].IsRoot &&A[i].K < A[min2].K) min2 = i;
	}
}
int main()
{
	int y = 1, num = N;
	int min1=0, min2=0;
	for (int i = 0; i < N; i++) {
		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].K << endl;
}

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

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

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

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

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

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

調(diào)試試圖

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

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

權(quán)值正確為100，是根節(jié)點(diǎn)，因?yàn)橹挥幸粋€(gè)根結(jié)點(diǎn)，沒(méi)法繼續(xù)合成新節(jié)點(diǎn)，程序結(jié)束。

總結(jié)

哈夫曼在算法和數(shù)據(jù)結(jié)構(gòu)中都挺重要的，只是不同場(chǎng)景下實(shí)現(xiàn)的方法和形式會(huì)有所不同，但就算千變?nèi)f化也離不開(kāi)最基礎(chǔ)的“二合一”形式，我提出的這個(gè)哈夫曼是不難理解的，希望對(duì)大家有所幫助，共同進(jìn)步?。。?/p>

到此這篇關(guān)于C++使用數(shù)組來(lái)實(shí)現(xiàn)哈夫曼樹(shù)的文章就介紹到這了,更多相關(guān)C++哈夫曼樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論