寫在前面

哈夫曼樹又稱最優(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）。可以證明霍夫曼樹的WPL是最小的；但是今天，咱們不談哈夫曼編碼，就只用結(jié)構(gòu)體配合數(shù)組來完成哈夫曼樹的生成，目標是得到正確的所有權(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：重復步驟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)造一棵哈夫曼編碼樹，具體過程如下：

理解代碼

源碼：

#include <iostream>
using namespace std;
#define N 8
struct Node 
{
	char L;//字母
	int K;//權(quán)值
	bool IsRoot;//是否為根結(jié)點
	int Lc, Rc;//左右子樹
	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é)點 Node 結(jié)構(gòu)體，并給他定義了五個屬性，分別是字符、權(quán)值、布爾型根結(jié)點標志、以及左右子樹。隨后直接定義Node類型數(shù)組Node(char l,int k,bool isRoot)，初始化Node A數(shù)組的長度為 N+N-1的原因是：選取兩個最小權(quán)值生成新的結(jié)點，并把結(jié)點放入A數(shù)組中，相當于每兩個結(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é)點的生成，逐漸++，然后默認最小值為數(shù)組的最后一個元素，利用一重for循環(huán)遍歷出最小值和次小值，這里注意，找出的最小值必須是根結(jié)點才可以，參加過生成新結(jié)點的都要把IsRoot設(shè)為false，次小值就是在不等于最小值的情況下找出最小值。

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

主函數(shù)中利用一重for循環(huán)調(diào)用FindMin函數(shù)找出兩個最小權(quán)值結(jié)點并默認放到數(shù)組的num位置上，即為最后一個位置；首先新節(jié)點的權(quán)值由兩個最小權(quán)值相加，并把新節(jié)點的左右子樹設(shè)為找到的兩個最小權(quán)值結(jié)點，由于結(jié)構(gòu)體數(shù)組默認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]組成的，可以確認權(quán)值沒有問題，A[8]能參加新節(jié)點的合成說明我們成功的把他設(shè)置為了根結(jié)點，然后直接看最后一個結(jié)點的信息；

權(quán)值正確為100，是根節(jié)點，因為只有一個根結(jié)點，沒法繼續(xù)合成新節(jié)點，程序結(jié)束。

總結(jié)

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

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

最新評論