C++深入講解哈夫曼樹

2022-05-25 14:02:55

哈夫曼樹的基本概念

Q：什麼是哈夫曼樹

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

1）路徑

Q：什麼是路徑

A：從樹中一個結點到另一個結點之間的分支構成這兩個結點之間的路徑。

2）路徑長度

Q：什麼是路徑長度

A：路徑上的分支數目稱作路徑長度。如圖根結點到結點B的路徑長度為2

3）權

Q：什麼是權

A：若將樹中結點賦給一個帶有某種含義的數值，則該數值稱為該結點的權。如圖A的權是7

4）結點的帶權路徑長度

Q：什麼是結點的帶權路徑長度

A：從該結點到樹根之間的路徑長度與結點上權的乘積

5）樹的帶權路徑長度

Q：什麼是樹的帶權路徑長度

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

6）哈夫曼樹

Q：什麼是樹的帶權路徑長度

A：給定n個權值作為n個葉子結點，構造一棵二元樹，若該樹的帶權路徑長度達到最小，則稱該二元樹為哈夫曼樹，也被稱為最優二元樹。

Q：哈夫曼樹中具有不同權值的葉子結點的分佈有什麼特點呢？

A：從上面的例子中，可以直觀的發現，在哈夫曼樹中，權值越大的結點離根結點越近。根據這個特點，哈夫曼最早給出了一個構造哈夫曼樹的方法，稱為哈夫曼演演算法。

哈夫曼樹的構造演演算法

哈夫曼樹的構造過程

Q：假設有4個葉子結點，權重依次是7，5，2，4，如何構建一顆哈夫曼樹，也就是帶權路徑長度最小的樹呢？

第一步：將這4個結點分別作為4棵僅含有一個結點的二元樹，形成一個森林

第二步：選擇當前權值最小的兩個結點C和D，根據這兩個結點生成一個新的父結點，父節點的權值是這兩個結點權值之和

第三步：選擇當前權值最小的兩個結點，再次根據這兩個結點生成一個新的父結點。現在剩下的結點有7，6，5，我們根據6和5生成新的父節點。

第四步：選擇當前權值最小的兩個結點，再次根據這兩個結點生成一個新的父結點。現在剩下的結點有7，11，我們根據7和11生成新的父節點。

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

哈夫曼樹演演算法的實現

1）結點的儲存結構

哈夫曼樹是一種二元樹，樹中每個結點要包含其雙親資訊和孩子結點的資訊，由此，每個結點的儲存結構如圖：

typedef struct{ 
	int weight;		 			//結點的權值
	int parent,lchild,rchild; 	//結點的雙親、左孩子、右孩子的下標
) HTNode,*HuffmanTree; 			//動態分配陣列儲存哈夫曼樹

2）構建哈夫曼樹

構建哈夫曼樹主要分為兩大部步

第一步為森林結點的初始化，第二步為哈夫曼樹的建立。

程式碼演示

void CreateHuffmanTree(HuffmanTree &HT,int n) 
{//構造哈夫曼樹 HT
	if(n<=1) return; 
	m=2*n-1; 
	HT=new HTNode[m+1]; 		//0 號單元未用，所以需要動態分配 m+l 個單元， HT[m)表示根結點
	for(i=1;i<=m;++i) 			//將l~m號單元中的雙親、左孩子，右孩子的下標都初始化為0
	{
		HT[i].parent=O;
		HT[i].lchild=O;
		HT[i].rchild=O;
	} 
	for(i=1;i<=n;++i)			//輸人前 n 個單元中葉子結點的權值
		cin>>HT[i].weight; 
	for(i=n+1;i<=m;++i)
	{//通過 n-1 次的選擇、刪除 、 合併來建立哈夫曼樹
		Select (HT,i-1,s1,s2); 
		//在 HT[k] 中選擇兩個其雙親域為 0 且權值最小的結點，並返回它們在 HT 中的序號 s1和 s2
		HT[s1].parent=i;
		HT[s2].parent=i; 
		//得到新結點 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 的權值為左右孩子權值之和
	}
}

到此這篇關於C++深入講解哈夫曼樹的文章就介紹到這了,更多相關C++哈夫曼樹內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！