C语言哈夫曼树的实现及递归实现哈夫曼编码

我不是女神ヾ 2022-12-17 07:26 121阅读 0赞

构建哈夫曼树算法的实现可以分为两大部分。

（1）**初始化**：首先动态申请2n个单元；然后循环2n-1次，从1号单元开始，依次将1至2n-1所有单元中的双亲、左孩子、右孩子的下标都初始化为0；最后再循环n次，输入前n个单元中叶子结点的权值。完成初始化的状态图为图中的（a）。

（2）**创建树**：循环n-1次，通过n-1次的选择、删除与合并来创建哈夫曼树。选择是从当前森林中选择双亲为0且权值最小的两个树根结点s1和s2；删除是指将结点s1和s2的双亲改为非0；合并就是将sl和s2的权值和作为一个新结点的权值依次存人到数组的第n+1之后的单元中，同时记录这个新结点左孩子的下标为s1，右孩子的下标为s2。完成此步骤的状态图为图中的（b）。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]  
完整代码如下：

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct
    { 
    	int weight;//结点的权值 
    	int parent,lchild,rchild;//结点的双亲，左孩子，右孩子的下标 
    }HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树 
    
    void InitTree(HuffmanTree &H,int &n)//初始化哈夫曼树 
    { 
    	int i,a;
    	printf("请输入结点个数： "); 
    	scanf("%d",&n);//结点个数 
    	H = (HTNode*)malloc(sizeof(HTNode)*(2*n));//申请一个2*n的空间 
    	for(i=0;i<2*n;i++)//利用循环对申请的空间进行初始化 
    		H[i].weight = H[i].parent = H[i].lchild = H[i].rchild = 0;
    	printf("分别为： "); 
    	for(i=0;i<n;i++)//利用循环对n个结点权值赋值 
    	{ 
    		scanf("%d",&a);
    		H[i+1].weight = a;
    	}
    }
    
    void Select(HuffmanTree H,int n,int &s1,int &s2)//选择函数 ，输入要循环的总次数n，并返回其权值最小的两个数的结点序号s1和s2 
    { 
    	int i,//循环次数i
    		a,//权值赋值变量 
    		b;//结点序号赋值变量 
    	for(i=0;i<n;i++)//循环赋值 
    	{ 
    		if(H[i+1].parent == 0)//找出第一个parent是0的结点，对变量a,b进行赋值 
    		{ 
    			a = H[i+1].weight;
    			b = i+1;
    			break;//循环终止条件 
    		}
    	}
    	for(i=0;i<n;i++)//利用循环找出最小值 
    	{ 
    		if(a>H[i+1].weight && H[i+1].parent == 0)// parent为0的结点的中的最小值， 赋值给a和b,b为序号 
    		{ 
    			a = H[i+1].weight;
    			b = i+1;
    		}
    	}
    	s1 = b;
    	for(i=0;i<n;i++)
    	{ 
    		if(H[i+1].parent == 0 && (i+1)!= s1)//找出第一个parent是0且不是最小权值的结点，对变量a,b进行赋值 
    		{ 
    			a = H[i+1].weight;
    			b = i+1;
    			break;
    		}
    	}
    	for(i=0;i<n;i++)//利用循环找出除s1的最小值 
    	{ 
    		if(a>H[i+1].weight && H[i+1].parent == 0 && (i+1)!=s1)
    		{ 
    			a = H[i+1].weight;
    			b = i+1;
    		}
    	}
    	s2 = b;
    }
    
    void CreateHuffmanTree(HuffmanTree &H,int n)//哈夫曼树的创建 
    { 
    	int s1,s2;//申请变量，方便接挑选函数返回的值 
    	int i;
    	for(i=n+1;i<2*n;i++)//通过n-1次的选择，删除，合并来构建哈夫曼树 
    	{ 
    		Select(H,i-1,s1,s2);//选出最小的两个数 
    		H[s1].parent = i;
    		H[s2].parent = i;//得到新结点i，从森林中删除s1，s2，并将s1,s2的双亲域由0改成i 
    		H[i].lchild = s1;
    		H[i].rchild = s2;//s1和s2分别作为i的左右孩子 
    		H[i].weight = H[s1].weight+H[s2].weight;//i的权值为左右孩子的权值之和 
    	}
    }
    
    void CreatHuffmanCode(HuffmanTree H,int n)//哈夫曼编码的输出，递归实现
    { 
    	if(H[n].parent == 0)//递归终止条件 
    		return ;
    	CreatHuffmanCode(H,H[n].parent);//递归双亲结点 
    	if(H[H[n].parent].lchild == n)//如果n的双亲的左孩子等于n，则输出0，否则输出1 
    		printf("0");
    	else
    		printf("1");
    }
    //书上的例子：8个结点分别为 5 29 7 8 14 23 3 11
    int main()
    { 
    	int n,i;
    	HuffmanTree H;
    	InitTree(H,n);//初始化 
    	CreateHuffmanTree(H,n);//构建哈夫曼树 
    	for(i=1;i<2*n;i++)//利用循环分别打印权值，双亲，左孩子，右孩子 
    	{ 
    		printf(  "%d ",H[i].weight);
    		printf("%d ",H[i].parent);
    		printf("%d ",H[i].lchild);
    		printf("%d\n",H[i].rchild);
    	}
    	printf("哈夫曼编码：\n");
    	for(i=1;i<=n;i++) //利用循环打印各个结点的哈夫曼编码 
    	{ 
    		printf("%d: ",i);
    		CreatHuffmanCode(H,i);//哈夫曼编码 
    		printf("\n");
    	}	
    	return 0;
    }

结果图展示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center 1]  
前两行为输入的数据。  
（完）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/0b9b8cf793c8495f8faa81a8416afcbd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/56068b5382314af69cbcf1650fd3fba3.png