C语言-哈夫曼树与哈夫曼编码的实现

喜欢ヅ旅行 2022-12-19 13:16 190阅读 0赞

## C语言-哈夫曼树与哈夫曼编码的实现 ##

### 1、什么是哈夫曼树 ###

**结点的权**：树中的结点被赋予一个表示某种意义的数值；  
**结点的带权路径长度**：从树的根到任意结点的路径长度（经过的边数）与该结点上权值的乘积；  
**树的带权路径长度（WPL）**： W P L = ∑ i = 1 n w i l i WPL = \\sum\\limits\_\{i=1\}^nw\_il\_i WPL=i=1∑nwili  
 w i w\_i wi是第i个叶结点所带的权值， l i l\_i li是该叶结点到根结点的路径长度；  
**哈夫曼树**：在含有n个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树；

--------------------

### 2、哈夫曼树的构造 ###

**哈夫曼树的构造过程**：

给定n个权值分别为 w 1 w\_1 w1, w 2 w\_2 w2,…, w n w\_n wn的结点：

*  将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F；
 *  构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左右子树，新结点的权值为左右子树根结点的权值之和；
 *  从F中删除刚才选出的两棵树，同时将新得到的树加入F中；
 *  重复2,3，直到F中只剩下一棵树为止；

以如下结点为例，构造一棵哈夫曼树：  
结点：\{a:45 , b:13 , c:12 , d:16 , e:9 , f:5\}  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center]  
**哈夫曼树的特点：**

*  每个初始结点最终都是叶结点，且权值越小的结点到根结点的路径越大；
 *  构造过程中共新建了n-1个结点，因此哈夫曼树的结点总数为2n-1；
 *  哈夫曼树中不存在度为1的结点；

--------------------

### 3、哈夫曼编码 ###

**哈夫曼编码**：又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。  
该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码(有时也称为霍夫曼编码)。

**由哈夫曼树得到哈夫曼编码**：可将字符的编码解释为从根至该字符的路径上边标记的序列，其中一般边标记0表示左孩子，标记1表示右孩子。

--------------------

### 3、哈夫曼树与哈夫曼编码的代码实现 ###

**哈夫曼树与哈夫曼编码的结构体：**

//赫夫曼树结点
    typedef struct
    {
        
    	int weight;//权值
    	int parent, lchild, rchild;
    }HTNode,*HTTree;
    
    //赫夫曼编码
    typedef struct
    {
        
    	char ch;//结点名称
    	char code[10];//结点的编码
    }CodeNode,*HuffmanCode;

**哈夫曼树的初始化：**

//赫夫曼树的初始化,m表示赫夫曼树总的结点个数
    void InitHuffmanTree(HTTree &HT, int m)
    {
        
    	HT=(HTTree)malloc(m * sizeof(HTNode));//为赫夫曼树结点申请空间
    
    	//赫夫曼树结点的初始化
    	for (int i = 0; i < m; i++)
    	{
        
    		HT[i].weight = 0;
    		HT[i].parent = -1;
    		HT[i].lchild = -1;
    		HT[i].rchild = -1;
    	}
    }

**哈夫曼树挑选2个最小权值的结点(重点)：**

//从n个结点中选取2个最小的结点,将其下标保存到min1,min2
    void SelectMin(HTTree &HT, int n, int &min1, int &min2)
    {
        
    	//临时结点，保存没有父结点的结点
    	typedef struct
    	{
        
    		int LocWeight;
    		int loc;//结点原始的下标
    	}TempNode,*TempTree;
    
    	int i, j=0;
    	int m1, m2;
    	m1 = m2 = 0;
    
    	TempTree temptree = (TempTree)malloc(n * sizeof(TempNode));
    
    	//将无父结点的结点存入temptree
    	for (i = 0; i < n; i++)
    	{
        
    		if (HT[i].parent == -1 && HT[i].weight != 0)
    		{
        
    			temptree[j].LocWeight = HT[i].weight;
    			temptree[j].loc = i;
    			j++;
    		}
    	}
    
    	//选择权值最小的结点
    	for (i = 0; i < j; i++)
    	{
        
    		if (temptree[i].LocWeight < temptree[m1].LocWeight)//不取等号，让其选择前面最小的结点
    			m1 = i;
    	}
    
    	//选择权值次小的结点
    	for (i = 0; i < j; i++)
    	{
        
    		if (m1 == m2)
    			m2++;//当m1在第一个位置时，m2后移一位
    		if (i != m1 && temptree[i].LocWeight <= temptree[m2].LocWeight)
    			m2 = i;
    	}
    	min1 = temptree[m1].loc;
    	min2 = temptree[m2].loc;
    }

**哈夫曼树的创建：**

//由n个结点创建HuffmanTree
    void CreateHuffmanTree(HTTree &HT, int weigh[],int n)
    {
        
    	int total = 2 * n - 1;//HuffmanTree中总的结点个数
    	int i, min1, min2;
    
    	InitHuffmanTree(HT, total);
    
    	for (i = 0; i < n; i++)
    		HT[i].weight = weigh[i];
    
    	//每次选择两个权值最小的结点合并
    	for (i = n; i < total; i++)
    	{
        
    		SelectMin(HT, i, min1, min2);
    		HT[min1].parent = i;
    		HT[min2].parent = i;
    		HT[i].lchild = min1;
    		HT[i].rchild = min2;
    		HT[i].weight = HT[min1].weight + HT[min2].weight;
    	}
    
    }

**哈夫曼编码的创建：**

注意：这里采用的方法是从叶子结点向根结点遍历的方式，保存哈夫曼编码，在实现时要注意字符的赋值问题。

//HuffmanCode的创建
    void CreateHuffmanCode(HTTree &HT, HuffmanCode &HC, char codename[], int n)
    {
        
    	int i, start,par,c;
    	char *cd = (char *)malloc(n * sizeof(char ));
    	cd[n-1] = '\0';//临时存储编码
    
    	HC = (HuffmanCode)malloc(n * sizeof(CodeNode));
    
    	//为每个结点创建HuffmanCode
    	for (i = 0; i < n; i++)
    	{
        
    		HC[i].ch = codename[i];
    		start = n - 1;
    		c = i;
    
    		//从叶子结点向上查找到根
    		while ((par = HT[c].parent) >= 0)
    		{
        
    			--start;
    
    			//看c是父结点的左子树还是右子树
    			if (HT[par].lchild == c)
    				cd[start] = '0';
    			else
    				cd[start] = '1';
    			c = par;
    		}
    
    		int g = 0;
    		for (int l = start; l < n; l++)
    			HC[i].code[g++] = cd[l];
    	}
    	free(cd);
    }

**哈夫曼编码的输出函数：**

void OutPutHuffmanCode(HuffmanCode HC, int n)
    {
        
    
    	for (int i = 0; i < n; i++)
    		printf("%c: %s\n", HC[i].ch, HC[i].code);
    
    }

至此，哈夫曼树与哈夫曼编码的函数实现都已完成，接下来在main函数中测试一下，与下面这种图对比。

int main()
    {
        
    	int n = 6;
    	char codename[6] = {
         'a','b','c','d','e','f' };
    	int weigh[6] = {
         45,13,12,16,9,5 };
    
    	HTTree HT;
    	HuffmanCode HC;
    
    	CreateHuffmanTree(HT, weigh, n);
    	CreateHuffmanCode(HT, HC, codename, n);
    	OutPutHuffmanCode(HC, n);
    
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center 2]

--------------------

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/0463d67c62674655abd04c7bcb1502b7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/0d6e592a4fcb4610b0ccd7a94a06bfb5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/a51ea81712b140f09f28f07e5d718fef.png