哈夫曼树的创建及哈夫曼编码的求解

哈夫曼树的创建及哈夫曼编码的求解：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXLEAF 1000   //最多叶子节点数
#define MAXVALUE 2147483647  //最大权值

/*哈夫曼树的数据结构*/
typedef struct
{
	int weight; //权值
	int parent; //父节点下标
	int lchild; //左孩子节点的下标
	int rchild; //右孩子节点的下标
} HNodeType;

/*函数声明列表*/
void HuffmanTree(HNodeType HuffNode[], int n);                     //1 创建哈夫曼树
void Output(HNodeType HuffNode[], int n);                          //2 输出所有节点的权值
void GetCode1(HNodeType HuffNode[], int i, char dest[], int len);  //3 通过递归求哈夫曼编码
void GetCode2(HNodeType HuffNode[], int n);                        //4 通过循环求哈夫曼编码

int main(void)
{
	int n = 7;
	printf("输入节点个数：");
	scanf("%d", &n);
	printf("输入各节点的权值：");
	HNodeType HuffNode[MAXLEAF];
	HuffmanTree(HuffNode, n);
	printf("所有节点权值：");
	Output(HuffNode, n);
	char dest[MAXLEAF] = "";
	printf("\n通过递归求各节点哈夫曼编码：\n");
	printf("%-8s%-10s\n", "权值", "编码");
	GetCode1(HuffNode, 2 * n - 2, dest, 0);
	printf("\n通过循环求各节点哈夫曼编码：\n");
	printf("%-8s%-10s\n", "权值", "编码");
	GetCode2(HuffNode, n);
	printf("\n");
	return 0;
}

/*函数实现部分*/
/*【功能1 创建哈夫曼树】*/
void HuffmanTree(HNodeType HuffNode[], int n)
{
	int i = 0, j = 0;
	for (i = 0; i < 2 * n - 1; i++)
	{
		HuffNode[i].weight = 0;
		HuffNode[i].parent = -1;
		HuffNode[i].lchild = -1;
		HuffNode[i].rchild = -1;
	}
	for (i = 0; i < n; i++) scanf("%d", &HuffNode[i].weight);
	//找最小值和次小值
	for (i = 0; i < n - 1; i++)
	{
		int m1 = MAXVALUE, m2 = MAXVALUE, x1 = -1, x2 = -1;
		for (j = 0; j < n + i; j++)
		{
			if (HuffNode[j].weight < m1 && HuffNode[j].parent == -1)
			{
				m2 = m1;
				x2 = x1;
				m1 = HuffNode[j].weight;
				x1 = j;
			}
			else if (HuffNode[j].weight < m2 && HuffNode[j].parent == -1)
			{
				m2 = HuffNode[j].weight;
				x2 = j;
			}
		}
		//选中x1,x2合并
		HuffNode[n + i].weight = m1 + m2;
		HuffNode[n + i].lchild = x1;
		HuffNode[n + i].rchild = x2;
		HuffNode[x1].parent = n + i;
		HuffNode[x2].parent = n + i;
	}
}

/*【功能2 输出所有节点的权值】*/
void Output(HNodeType HuffNode[], int n)
{
	int i = 0;
	for (i = 0; i < 2 * n - 1; i++)
	{
		printf("%d ", HuffNode[i].weight);
	}
	printf("\n");
}

/*【功能3 通过递归求哈夫曼编码】*/
void GetCode1(HNodeType HuffNode[], int i, char dest[], int len)
{
	if (HuffNode[i].lchild == -1 && HuffNode[i].rchild == -1)
	{
		dest[len] = '\0';
		printf("%-8d%-10s\n",  HuffNode[i].weight, dest);
		return;
	}
	if (HuffNode[i].lchild != -1)
	{
		dest[len] = '0';
		GetCode1(HuffNode, HuffNode[i].lchild, dest, len + 1);
	}
	if (HuffNode[i].rchild != -1)
	{
		dest[len] = '1';
		GetCode1(HuffNode, HuffNode[i].rchild, dest, len + 1);
	}
}

/*【功能4 通过循环求哈夫曼编码】*/
void GetCode2(HNodeType HuffNode[], int n)
{
	int i = 0;
	for (i = 0; i < n; i++)
	{
		int c = i, f = 0, j = 0;
		int code[MAXLEAF] = { 0 }; //编码数组
		int len = 0;
		f = HuffNode[c].parent;
		while (f >= 0)
		{
			if (HuffNode[f].lchild == c) code[len++] = 0;
			else code[len++] = 1;
			c = f;
			f = HuffNode[c].parent;
		}
		printf("%-8d", HuffNode[i].weight);
		for (j = len - 1; j >= 0; j--) printf("%d", code[j]);
		printf("\n");
	}
}

执行结果：