目錄

一、哈夫曼樹

? ?1.哈夫曼樹的基本概念

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

? ?3.哈夫曼樹的的實(shí)現(xiàn)

二、哈夫曼編碼

? ? 1.有關(guān)哈夫曼樹編碼的兩個(gè)概念

? ? 2.哈夫曼樹編碼滿足的兩個(gè)性質(zhì)

? ? 3.哈夫曼編碼的實(shí)現(xiàn)

三、例題（含完整代碼及詳細(xì)注解）

? ? 1.題目

? ? 2.代碼實(shí)現(xiàn)

? ? 3.結(jié)果截圖

一、哈夫曼樹

1.哈夫曼樹的基本概念

• 路徑：從樹中的一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。
• 路徑長度：路徑上的分支數(shù)目稱作路徑長度。
• 樹的路徑長度：從樹根到每一結(jié)點(diǎn)的路徑長度之和。
• 權(quán)：賦予某個(gè)實(shí)體的 一個(gè)量，是對實(shí)體的某個(gè)或某些屬性的數(shù)值化描述。在數(shù)據(jù)結(jié)構(gòu)中，實(shí)體有結(jié)點(diǎn)和邊兩大類，所以對應(yīng)有結(jié)點(diǎn)權(quán)和邊權(quán)。
• 結(jié)點(diǎn)的帶權(quán)路徑長度：從該結(jié)點(diǎn)到樹根之間的路徑長度與結(jié)點(diǎn)上的全的乘積。
• 樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度與結(jié)點(diǎn)上權(quán)的乘積。
• 哈夫曼樹：假設(shè)有m個(gè)權(quán)值,可以構(gòu)造一顆含n個(gè)葉子結(jié)點(diǎn)的二叉樹，則其中帶權(quán)路徑長度WPL的最小二叉樹稱作最優(yōu)二叉樹或哈夫曼樹。

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

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

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

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

口訣：1.構(gòu)造森林全是根

? ? ? ? ? ?2.選用兩小造新樹

? ? ? ? ? ?3.刪除兩小添新人

? ? ? ? ? ?4.重復(fù)2、3剩單根

?3.哈夫曼樹的實(shí)現(xiàn)

? 算法步驟：

1. 初始化:首先動(dòng)態(tài)申請2n個(gè)單元;然后循環(huán)2n-1次，從1號(hào)單元開始，依次將1至2n-l所有單元中的雙親、左孩子、右孩子的下標(biāo)都初始化為0;最后再循環(huán)n次，輸入前n個(gè)單元中葉子結(jié)點(diǎn)的權(quán)值。
2. 創(chuàng)建樹:循環(huán)n-1次，通過n-1次的選擇、 刪除與合并來創(chuàng)建哈夫曼樹。選擇是從當(dāng)前森林中選擇雙親為0且權(quán)值最小的兩個(gè)樹根結(jié)點(diǎn)sl和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){
	//構(gòu)造哈夫曼樹
	if(n<=1)  return;
	int m=2*n-1;
	HT=new HTNode[m+1]; //0單元號(hào)未用，下標(biāo)從1開始 
	for(int i=1;i<=m;i++){ //初始化，將下標(biāo)1~m號(hào)結(jié)點(diǎn)的雙親，左孩子，右孩子置為0 
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
	} 
	for(int i=1;i<=n;i++){
		cin >> HT[i].weight;  //輸入前n個(gè)結(jié)點(diǎn)的權(quán)值 
	} 
// 初始化結(jié)束，下面創(chuàng)開始創(chuàng)建哈夫曼樹
//---------------------------------------------------------	
 for(int i=n+1;i<=m;i++){
 	/* 在select函數(shù)中，在前n個(gè)結(jié)點(diǎn)中通過n-1次的選擇兩個(gè)權(quán)值較小的結(jié)點(diǎn),
	 進(jìn)行合并，刪除 來創(chuàng)建哈夫曼樹 */
	 int s1=0,s2=0;
 	Select(HT,i-1,&s1,&s2);
 	/* 在select中挑選出兩個(gè)權(quán)值較小的結(jié)點(diǎn)，且s1<s2；
	 合并成一個(gè)新的結(jié)點(diǎn)，新的結(jié)點(diǎn)的結(jié)點(diǎn)號(hào)為i ,此時(shí)s1和s2結(jié)點(diǎn)的雙親結(jié)點(diǎn)即為i */
 	HT[s1].parent=i; HT[s2].parent=i;
 	HT[i].lchild=s1;//將s1和s2分別作為結(jié)點(diǎn)i的左右孩子 
 	HT[i].rchild=s2;
 	HT[i].weight=HT[s1].weight+HT[s2].weight;//結(jié)點(diǎn)i的權(quán)值為左右孩子之和 
 } 

}

//Select函數(shù) 
void Select(HuffmanTree HT,int end,int *s1,int *s2){
	int min1,min2;//min1存放較小的，min2存放第二小的,min1<min2
	//先挑選出一個(gè)雙親結(jié)點(diǎn)為0的結(jié)點(diǎn) ，如果雙親節(jié)點(diǎn)不為0說明這個(gè)結(jié)點(diǎn)已經(jīng)在生成新節(jié)點(diǎn)中被使用過 
	int i=1;
	while(HT[i].parent!=0&&i<=end){
		i++;
	}
	//將第一次挑選出來的結(jié)點(diǎn)的權(quán)值先賦值給min1，然后i加一，挑選第二個(gè)雙親結(jié)點(diǎn)為0的結(jié)點(diǎn)
	min1=HT[i].weight;
	*s1=i;
	i++;
	// 挑選第二個(gè)雙親結(jié)點(diǎn)為0的結(jié)點(diǎn)
	while(HT[i].parent!=0&&i<=end){
		i++;
	}
	/*對挑選出來的第一個(gè)結(jié)點(diǎn)第二個(gè)結(jié)點(diǎn)再進(jìn)行權(quán)值的比較，如果第二次挑選出來的HT[i].weight
	小于min1的值，則先將min1的值付給min2,再將HT[i].weight賦給min1; 如果第二次挑選出來的
	HT[i].weight大于min1的值，則將HT[i].weight賦給min2
	*/
	if(HT[i].weight<min1){
		min2=min1;
		*s2=*s1;
		min1=HT[i].weight;
		*s1=i;
	}else{
		min2=HT[i].weight;
		*s2=i;
	}
	//對余下的結(jié)點(diǎn)進(jìn)行遍歷
	for(int j=i+1;j<=end;j++){
		if(HT[j].parent!=0) continue;
		if(HT[j].weight<min1){
			min2=min1;
			min1=HT[j].weight;
			*s2=*s1;
			*s1=j;
		}
		//如果 min1<=HT[i].weight<=min2,則 將HT[j].weight的值賦給min2
		else if(HT[j].weight>=min1&&HT[j].weight<min2){
			min2=HT[j].weight;
			*s2=j;
		}	
		
	} 
}

二、哈夫曼編碼

1.有關(guān)哈夫曼樹編碼的兩個(gè)概念

• 前綴編碼:如果在一個(gè)編碼方案中， 任一個(gè)編碼都不是其他任何編碼的前綴(最左子串)，如稱編碼是前綴編碼。例如，案例5.1中的第2種編碼方案的編碼0, 10, 110,111是前綴編碼，而第3種編碼方案的編碼0，01, 010, 111 就不是前綴編碼。前綴編碼可以保證對壓縮文件進(jìn)行解碼時(shí)不產(chǎn)生二義性，確保正確解碼。
• 哈夫曼編碼:對一棵具有n個(gè)葉子的哈夫曼樹，若對樹中的每個(gè)左分支賦予0，右分支賦予1,則從根到每個(gè)葉子的路徑上，各分支的賦值分別構(gòu)成一一個(gè)二進(jìn)制串，該二進(jìn)制串就稱為哈夫曼編碼。

2.哈夫曼樹編碼滿足的兩個(gè)性質(zhì)

• 性質(zhì)1 ?哈夫曼編碼是前綴編碼

  哈夫曼編碼是根到葉子路徑上的編碼序列，由樹的特點(diǎn)知，若路徑A是另一條路徑B的最左部分，則B經(jīng)過了A.則A的終點(diǎn)一定不是葉子，而哈夫曼編碼對應(yīng)路徑的終點(diǎn)一定為葉子，因此，任一哈夫曼碼都不會(huì)與任意其他哈夫曼編碼的前綴部分完全重疊，因此哈夫曼編碼是前綴編碼。

• 性質(zhì)2 ?哈夫曼編碼是最優(yōu)前綴編碼

  對于包括n個(gè)字符的數(shù)據(jù)文件，分別以它們的出現(xiàn)次數(shù)為權(quán)值構(gòu)造哈夫曼樹，則利用該樹對應(yīng)的哈夫曼編碼對文件進(jìn)行編碼，能使該文件壓縮后對應(yīng)的二進(jìn)制文件的長度最短。

3.哈夫曼編碼的實(shí)現(xiàn)

算法步驟：

1. 分配存儲(chǔ)刀個(gè)字符編碼的編碼表空間HC,長度為n+1:;分配臨時(shí)存儲(chǔ)每個(gè)字符編碼的動(dòng)態(tài)數(shù)組空間cd, cd[n-1]置為'\0'。
2. 逐個(gè)求解n個(gè)字符的編碼，循環(huán)n次，執(zhí)行以下操作:

• 設(shè)置變量start用于記錄編碼在cd中存放的位置，start 初始時(shí)指向最后，即編碼結(jié)束符位置n-1;
• 設(shè)置變量c用于記錄從葉子結(jié)點(diǎn)向上回溯至根結(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)下標(biāo)，c初始時(shí)為當(dāng)前待編碼字符的下標(biāo)i，f用于記錄i的雙親結(jié)點(diǎn)的下標(biāo);
• 從葉子結(jié)點(diǎn)向上回溯至根結(jié)點(diǎn)，求得字符i的編碼，當(dāng)f沒有到達(dá)根結(jié)點(diǎn)時(shí)，循環(huán)執(zhí)行以下操作:

? ? ? ? ? ?回溯一次start向前指一個(gè)位置，即--start;

? ? ? ? ? ?若結(jié)點(diǎn)c是f的左孩子，則生成代碼0，否則生成代碼1,生成的代碼0或1保存在cd[start]? ? ? ? ? ? ?中;
? ? ? ? ? ?繼續(xù)向上回溯，改變c和f的值。

• 根據(jù)數(shù)組cd的字符串長度為第i個(gè)字符編碼分配空間HC[i]，然后將數(shù)組cd中的編碼復(fù)制? ? 到HC[i]中。

? ? ?3. 釋放臨時(shí)空間cd。

typedef char **HuffmanCode;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼編碼表
 
void CreateHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n){
	//得到哈夫曼編碼 
	int start,c,f;
	HC=new char*[n+1];      //下表從1開始，分配存儲(chǔ)n個(gè)字符編碼的編碼表空間
	char* cd=new char[n];  //臨時(shí)存放每個(gè)字符編碼的動(dòng)態(tài)數(shù)組空間
	 cd[n-1]='\0';        //編碼結(jié)束符 
	for(int i=1;i<=n;i++){    //逐個(gè)字符求哈夫曼編碼 
		start=n-1;            //start開始指向最后，即編碼結(jié)束符的位置 
		c=i;f=HT[i].parent;   //f指向結(jié)點(diǎn)c的雙親結(jié)點(diǎn),
		while(f!=0){          
			start--;           //回溯一次，start位置向前指一個(gè)位置 
			if(HT[f].lchild==c) cd[start]='0'; //如果結(jié)點(diǎn)c是f的左孩子，則生成代碼0 
			else cd[start]='1';                //如果結(jié)點(diǎn)c是f的右孩子，則生成代碼0 
			c=f;f=HT[f].parent;                //繼續(xù)向上回溯，直至 f的雙親為0回溯結(jié)束 
		}   
		/* 注意：1.for循環(huán)是為了逐個(gè)字符求哈夫曼編碼；while循環(huán)是為了對所求字符進(jìn)行回溯，直至雙親為0
		         2.結(jié)點(diǎn)的雙親，左孩子，右孩子指向的全都是結(jié)點(diǎn)i，并不是結(jié)點(diǎn)的權(quán)值，這一點(diǎn)很容易混淆 
		*/                                    
		HC[i]=new char[n-start];    // 為第i個(gè)字符進(jìn)行編碼 
		strcpy(HC[i],&cd[start]);   //為第i個(gè)字符編碼分配空間 
	} 
	delete cd;                    //釋放臨時(shí)空間 
} 

三、?例題（含完整代碼及詳細(xì)注解）

1.題目

1. 一個(gè)單位有5個(gè)部門，每個(gè)部門都有一部電話，但是整個(gè)單位只有一根外線，當(dāng)有電話打過來的時(shí)候，由轉(zhuǎn)接員轉(zhuǎn)到內(nèi)線電話，已知各部門使用外線電話的頻率為（次/天）：5 16 9?12 19。利用哈夫曼樹算法思想設(shè)計(jì)內(nèi)線電話號(hào)碼，使得接線員撥號(hào)次數(shù)盡可能少要求：

? ? ? ? （1）依據(jù)使用外線電話的頻率構(gòu)造二叉樹。

? ? ? ? （2）輸出設(shè)計(jì)出的各部門內(nèi)線電話號(hào)碼。

2.代碼實(shí)現(xiàn)

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
typedef struct{
	int weight; 
	int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼編碼表

void CreateHuffmanTree(HuffmanTree &HT,int n);   //構(gòu)造哈夫曼樹 
void Select(HuffmanTree HT,int end,int *s1,int *s2);  //select函數(shù) 
void CreateHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n); //哈夫曼編碼 


void CreateHuffmanTree(HuffmanTree& HT,int n){
	//構(gòu)造哈夫曼樹
	if(n<=1)  return;
	int m=2*n-1;
	HT=new HTNode[m+1]; //0單元號(hào)未用，下標(biāo)從1開始 
	for(int i=1;i<=m;i++){ //初始化，將下標(biāo)1~m號(hào)結(jié)點(diǎn)的雙親，左孩子，右孩子置為0 
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
	} 
	for(int i=1;i<=n;i++){
		cin >> HT[i].weight;  //輸入前n個(gè)結(jié)點(diǎn)的權(quán)值 
	} 
// 初始化結(jié)束，下面創(chuàng)開始創(chuàng)建哈夫曼樹
//---------------------------------------------------------	
 for(int i=n+1;i<=m;i++){
 	/* 在select函數(shù)中，在前n個(gè)結(jié)點(diǎn)中通過n-1次的選擇兩個(gè)權(quán)值較小的結(jié)點(diǎn),
	 進(jìn)行合并，刪除 來創(chuàng)建哈夫曼樹 */
	 int s1=0,s2=0;
 	Select(HT,i-1,&s1,&s2);
 	/* 在select中挑選出兩個(gè)權(quán)值較小的結(jié)點(diǎn)，且s1<s2；
	 合并成一個(gè)新的結(jié)點(diǎn)，新的結(jié)點(diǎn)的結(jié)點(diǎn)號(hào)為i ,此時(shí)s1和s2結(jié)點(diǎn)的雙親結(jié)點(diǎn)即為i */
 	HT[s1].parent=i; HT[s2].parent=i;
 	HT[i].lchild=s1;//將s1和s2分別作為結(jié)點(diǎn)i的左右孩子 
 	HT[i].rchild=s2;
 	HT[i].weight=HT[s1].weight+HT[s2].weight;//結(jié)點(diǎn)i的權(quán)值為左右孩子之和 
 } 

}

//Select函數(shù) 
void Select(HuffmanTree HT,int end,int *s1,int *s2){
	int min1,min2;//min1存放較小的，min2存放第二小的,min1<min2
	//先挑選出一個(gè)雙親結(jié)點(diǎn)為0的結(jié)點(diǎn) ，如果雙親節(jié)點(diǎn)不為0說明這個(gè)結(jié)點(diǎn)已經(jīng)在生成新節(jié)點(diǎn)中被使用過 
	int i=1;
	while(HT[i].parent!=0&&i<=end){
		i++;
	}
	//將第一次挑選出來的結(jié)點(diǎn)的權(quán)值先賦值給min1，然后i加一，挑選第二個(gè)雙親結(jié)點(diǎn)為0的結(jié)點(diǎn)
	min1=HT[i].weight;
	*s1=i;
	i++;
	// 挑選第二個(gè)雙親結(jié)點(diǎn)為0的結(jié)點(diǎn)
	while(HT[i].parent!=0&&i<=end){
		i++;
	}
	/*對挑選出來的第一個(gè)結(jié)點(diǎn)第二個(gè)結(jié)點(diǎn)再進(jìn)行權(quán)值的比較，如果第二次挑選出來的HT[i].weight
	小于min1的值，則先將min1的值付給min2,再將HT[i].weight賦給min1; 如果第二次挑選出來的
	HT[i].weight大于min1的值，則將HT[i].weight賦給min2
	*/
	if(HT[i].weight<min1){
		min2=min1;
		*s2=*s1;
		min1=HT[i].weight;
		*s1=i;
	}else{
		min2=HT[i].weight;
		*s2=i;
	}
	//對余下的結(jié)點(diǎn)進(jìn)行遍歷
	for(int j=i+1;j<=end;j++){
		if(HT[j].parent!=0) continue;
		if(HT[j].weight<min1){
			min2=min1;
			min1=HT[j].weight;
			*s2=*s1;
			*s1=j;
		}
		//如果 min1<=HT[i].weight<=min2,則 將HT[j].weight的值賦給min2
		else if(HT[j].weight>=min1&&HT[j].weight<min2){
			min2=HT[j].weight;
			*s2=j;
		}	
		
	} 
}

void CreateHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n){
	//得到哈夫曼編碼 
	int start,c,f;
	HC=new char*[n+1];      //下表從1開始，分配存儲(chǔ)n個(gè)字符編碼的編碼表空間
	char* cd=new char[n];  //臨時(shí)存放每個(gè)字符編碼的動(dòng)態(tài)數(shù)組空間
	 cd[n-1]='\0';        //編碼結(jié)束符 
	for(int i=1;i<=n;i++){    //逐個(gè)字符求哈夫曼編碼 
		start=n-1;            //start開始指向最后，即編碼結(jié)束符的位置 
		c=i;f=HT[i].parent;   //f指向結(jié)點(diǎn)c的雙親結(jié)點(diǎn),
		while(f!=0){          
			start--;           //回溯一次，start位置向前指一個(gè)位置 
			if(HT[f].lchild==c) cd[start]='0'; //如果結(jié)點(diǎn)c是f的左孩子，則生成代碼0 
			else cd[start]='1';                //如果結(jié)點(diǎn)c是f的右孩子，則生成代碼0 
			c=f;f=HT[f].parent;                //繼續(xù)向上回溯，直至 f的雙親為0回溯結(jié)束 
		}   
		/* 注意：1.for循環(huán)是為了逐個(gè)字符求哈夫曼編碼；while循環(huán)是為了對所求字符進(jìn)行回溯，直至雙親為0
		         2.結(jié)點(diǎn)的雙親，左孩子，右孩子指向的全都是結(jié)點(diǎn)i，并不是結(jié)點(diǎn)的權(quán)值，這一點(diǎn)很容易混淆 
		*/                                    
		HC[i]=new char[n-start];    // 為第i個(gè)字符進(jìn)行編碼 
		strcpy(HC[i],&cd[start]);   //為第i個(gè)字符編碼分配空間 
	} 
	delete cd;                    //釋放臨時(shí)空間 
} 

int main(){
	HuffmanTree HT;
	HuffmanCode HC;
	cout<<"各部門使用外線電話的頻率為:"<<endl;
	CreateHuffmanTree(HT,5);
	CreateHuffmanCode(HT,HC,5);
	cout << "各部門內(nèi)線電話號(hào)碼" << endl;
	for (int i = 1; i <= 5; i++) {
		cout << HC[i] << endl;
	}
	return 0;
}

3.結(jié)果截圖?

?文章中還存在著瑕疵，希望各位大神指教? ??文章來源地址http://www.zghlxwxcb.cn/news/detail-469190.html

到了這里，關(guān)于哈夫曼樹的構(gòu)造和哈夫曼編碼實(shí)現(xiàn)詳細(xì)講解（含例題詳細(xì)講解）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！