哈夫曼樹的基本概念

Q：什么是哈夫曼樹

A：哈夫曼樹又稱最優(yōu)樹，是一類帶權(quán)路徑長度最短的樹。在正式了解哈夫曼樹之前，我們需要了解一些概念。

1）路徑

Q：什么是路徑

A：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。

2）路徑長度

Q：什么是路徑長度

A：路徑上的分支數(shù)目稱作路徑長度。如圖根結(jié)點(diǎn)到結(jié)點(diǎn)B的路徑長度為2

3）權(quán)

Q：什么是權(quán)

A：若將樹中結(jié)點(diǎn)賦給一個(gè)帶有某種含義的數(shù)值，則該數(shù)值稱為該結(jié)點(diǎn)的權(quán)。如圖A的權(quán)是7

4）結(jié)點(diǎn)的帶權(quán)路徑長度

Q：什么是結(jié)點(diǎn)的帶權(quán)路徑長度

A：從該結(jié)點(diǎn)到樹根之間的路徑長度與結(jié)點(diǎn)上權(quán)的乘積

5）樹的帶權(quán)路徑長度

Q：什么是樹的帶權(quán)路徑長度

A：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，通常記作 WPL。如圖WPL=7*1+5*2+2*3+4*3=35

6）哈夫曼樹

Q：什么是樹的帶權(quán)路徑長度

A：給定n個(gè)權(quán)值作為n個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹，若該樹的帶權(quán)路徑長度達(dá)到最小，則稱該二叉樹為哈夫曼樹，也被稱為最優(yōu)二叉樹。

Q：哈夫曼樹中具有不同權(quán)值的葉子結(jié)點(diǎn)的分布有什么特點(diǎn)呢？

A：從上面的例子中，可以直觀的發(fā)現(xiàn)，在哈夫曼樹中，權(quán)值越大的結(jié)點(diǎn)離根結(jié)點(diǎn)越近。根據(jù)這個(gè)特點(diǎn)，哈夫曼最早給出了一個(gè)構(gòu)造哈夫曼樹的方法，稱為哈夫曼算法。

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

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

Q：假設(shè)有4個(gè)葉子結(jié)點(diǎn)，權(quán)重依次是7，5，2，4，如何構(gòu)建一顆哈夫曼樹，也就是帶權(quán)路徑長度最小的樹呢？

第一步：將這4個(gè)結(jié)點(diǎn)分別作為4棵僅含有一個(gè)結(jié)點(diǎn)的二叉樹，形成一個(gè)森林

第二步：選擇當(dāng)前權(quán)值最小的兩個(gè)結(jié)點(diǎn)C和D，根據(jù)這兩個(gè)結(jié)點(diǎn)生成一個(gè)新的父結(jié)點(diǎn)，父節(jié)點(diǎn)的權(quán)值是這兩個(gè)結(jié)點(diǎn)權(quán)值之和

第三步：選擇當(dāng)前權(quán)值最小的兩個(gè)結(jié)點(diǎn)，再次根據(jù)這兩個(gè)結(jié)點(diǎn)生成一個(gè)新的父結(jié)點(diǎn)?，F(xiàn)在剩下的結(jié)點(diǎn)有7，6，5，我們根據(jù)6和5生成新的父節(jié)點(diǎn)。

第四步：選擇當(dāng)前權(quán)值最小的兩個(gè)結(jié)點(diǎn)，再次根據(jù)這兩個(gè)結(jié)點(diǎn)生成一個(gè)新的父結(jié)點(diǎn)?，F(xiàn)在剩下的結(jié)點(diǎn)有7，11，我們根據(jù)7和11生成新的父節(jié)點(diǎn)。

就這樣，我們得到了最終的二叉樹

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

1）結(jié)點(diǎn)的存儲結(jié)構(gòu)

哈夫曼樹是一種二叉樹，樹中每個(gè)結(jié)點(diǎn)要包含其雙親信息和孩子結(jié)點(diǎn)的信息，由此，每個(gè)結(jié)點(diǎn)的存儲結(jié)構(gòu)如圖：

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

2）構(gòu)建哈夫曼樹

構(gòu)建哈夫曼樹主要分為兩大部步

第一步為森林結(jié)點(diǎn)的初始化，第二步為哈夫曼樹的建立。

代碼演示

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

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

最新評論