哈夫曼树的构造C/C++代码实现

雨点打透心脏的1/2处 2023-02-16 15:28 24阅读 0赞

## 哈夫曼树： ##

所谓哈夫曼(Huffman)树就是最优二叉树，是带权路径长度WPL最小的二叉树。

## 哈夫曼树的构造： ##

根据哈夫曼树的特点：权值越大的结点离根结点越近。  
具体方法：依次选择权值最小的二个结点作为左右子树构造一颗新的二叉树，其产生的根结点的权值为左右子树权值之和。一直重复直到只含一棵树为止。‘

权值：  
![在这里插入图片描述][20200610140428122.png]  
哈夫曼树：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]

## 哈夫曼树的存储： ##

由于哈夫曼树中没有度为1 的结点，则一棵有n个叶子结点的哈夫曼树共有 2n-1个结点，可以存储在一个大小为2n-1的一维数组中。  
为了实现方便，数组的0号单元不使用，从1号单元开始使用，所以数组的大小为2n，。将叶子结点集中存储在前面部分 1~n个位置。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]

## 代码如下： ##

#include<stdio.h>
    #include<iostream>
    
    //哈夫曼树定义
    typedef struct {
        
    	int weight;
    	int parent, lchild, rchild;
    }HTNode, *HuffmanTree;
    
    //选择两个双亲域为0且权值最小的结点，并返回在HT中的序号s1，s2
    void Select(HuffmanTree &HT, int n, int &s1, int &s2)
    {
        
    	//寻找第一个双亲域为0且权值最小的结点
    	int min;
    	for (int i = 1; i <= n; i++)	//找到第一个双亲域为0的，下标暂存到min
    	{
        
    		if (HT[i].parent == 0)
    		{
        
    			min = i;
    			break;
    		}
    	}
    
    	for (int i = 1; i <= n; i++)
    	{
        
    		if (HT[i].parent == 0)
    		{
        
    			if (HT[i].weight < HT[min].weight)
    			{
        
    				min = i;
    			}
    		}
    	}
    	s1 = min;
    
    	//寻找第二个双亲域为0且权值最小的结点
    	for (int i = 1; i <= n; i++)	//找到第一个双亲域为0的，下标暂存到min
    	{
        
    		if (HT[i].parent == 0 && i != s1)
    		{
        
    			min = i;
    			break;
    		}
    	}
    
    	for (int i = 1; i <= n; i++)
    	{
        
    		if (HT[i].parent == 0 && i != s1)
    		{
        
    			if (HT[i].weight < HT[min].weight)
    			{
        
    				min = i;
    			}
    		}
    	}
    	s2 = min;
    }
    
    //输出
    void println(HuffmanTree &HT, int m)
    {
        
    	printf("==============================\n");
    	for (int i = 1; i <= m; i++)
    	{
        
    
    		printf("%d，   ", i);
    		printf("%d   ", HT[i].weight);
    		printf("%d   ", HT[i].parent);
    		printf("%d  ", HT[i].lchild);
    		printf("%d   \n", HT[i].rchild);
    		printf("---------------------------\n");
    	}
    }
    
    //创建哈夫曼树
    void CreateHuffmanTree(HuffmanTree &HT, int n)
    {
        
    	//初始化
    	int i, m = 2 * n - 1, s1, s2;		//m为所有结点的个数
    	if (n <= 1) return;
    	HT = new HTNode[m + 1];				//0号不用从1开始，多申请一行，前1~n存放叶子结点
    	for (i = 1; i <= m; ++i)			//遍历每一个结点并赋值为0
    	{
        
    		HT[i].parent = 0;
    		HT[i].lchild = 0;
    		HT[i].rchild = 0;
    	}
    
    	//创建树
    	for (i = 1; i <= n; ++i)			//把叶子结点权值放入表中
    	{
        
    		printf("请输入第%d个叶子：", i);
    		scanf("%d", &(HT[i].weight));
    	}
    
    	printf("\nHT的初态\n");
    	println(HT, m);
    	for (int i = n + 1; i <= m; ++i)     //从非叶子结点开始创建
    	{
        
    		Select(HT, i - 1, s1, s2);		//选择两个最小的结点
    
    		HT[s1].parent = i;
    		HT[s2].parent = i;				//把叶子结点双亲域赋上
    		HT[i].lchild = s1;
    		HT[i].rchild = s2;
    		HT[i].weight = HT[s1].weight + HT[s2].weight;
    	}
    	printf("\nHT的终态\n");
    	println(HT, m);
    }
    
    
    int main() {
        
    	HuffmanTree HT;
    	int n;								//n为叶子节点的个数
    	printf("请输入叶子节点的个数：");
    	scanf("%d", &n);
    
    	CreateHuffmanTree(HT, n);
    }

## 运行结果： ##

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

[20200610140428122.png]: https://img-blog.csdnimg.cn/20200610140428122.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200610140448635.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200610140716316.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200610140814746.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70