数据结构（C语言）哈夫曼树 11月25日

实验内容：

1．设置7个字符a~g的权值，以它们为叶子构造哈夫曼树

2. 输出它们的哈夫曼编码。

哈夫曼树：

#include<stdio.h>
#include<stdlib.h>
#include"string.h"
//哈夫曼树
#define MAXLEAF 100  //最多叶子节点数
#define MAXVALUE 100  //最大权值

typedef struct {
	int weight;//权值
	int parent;//父节点
	int lchild;//左孩子
	int rchild;//右孩子
}hnodetype;


int n = 7;//叶子节点个数，全局变量
//哈夫曼算法生成哈夫曼树（最优二叉树）
void huffmantree(hnodetype huffnode[MAXLEAF], int n) {
	int i = 0, j = 0;
	for (i = 0; i < 2 * n - 1; i++) //初始化huffnode数组
	{
		huffnode[i].weight = 0;  huffnode[i].parent = -1;
		huffnode[i].lchild = -1; huffnode[i].rchild = -1;
	}
	for (i = 0; i < n; i++)
		scanf_s("%d", &huffnode[i].weight);
	
	
	//找最小值与次小值
	for (i = 0; i < n - 1; i++) //找最小值m1和次小值m2循环 n - 1轮，如5个叶子节点要循环4次，所以是n-1
	{
		int m1, m2, x1, x2;

		m1 = m2 = MAXVALUE;//权值
		x1 = x2 = -1;//权值所在的下标
		//寻找最小值m1和次小值m2
		for (j = 0; j < n + i; j++) {
			if (huffnode[j].weight < m1 && huffnode[j].parent == -1) //当前值是j，和m1相比
				//加huffnode[j].parent == -1这个条件是为了排除已经有父节点的结点，即已经合并过的结点
				//进行合并的时候要选那些没有父节点的结点
			{
				m2 = m1;
				x2 = x1;
				m1 = huffnode[j].weight;
				x1 = j;
			}//如果j<m1，则m1变成当前值j，同时m2变成m1，x1变成j，x2变成x1
			else if (huffnode[j].weight < m2 && huffnode[j].parent == -1)
			{
				m2 = huffnode[j].weight;
				x2 = j;
			}//与m2相比，就把m2赋值为当前值j即可
		}
		//选中x1，x2进行合并
		huffnode[n + i].weight = m1 + m2;//合并后新节点的下标是n+i，i代表当前第几轮，第一轮i=0，新节点的权值为m1 + m2
		huffnode[n + i].lchild = x1; huffnode[n + i].rchild = x2;//对左右孩子进行赋值
		huffnode[x1].parent = n + i; huffnode[x2].parent = n + i;//修正下标x1和x2对应的父节点为新节点
	}
}

//输出所有节点的权值
void output(hnodetype huffnode[MAXLEAF], int n) {
	int i = 0;
	for (i = 0; i < 2 * n - 1; i++) {
		printf("%d\t", huffnode[i].weight);
	}
	printf("\n");
}
//求哈夫曼编码：递归做法
void getcode1(hnodetype huffnode[MAXLEAF], int i, char dest[], int len) 
//i是根节点的下标，dest[]是编码保存的地方，保存在一个字符串数组，len是长度
{
	if (huffnode[i].lchild == -1 && huffnode[i].rchild == -1) {
		dest[len] = 0;//字符串结束字符
		printf("%-6c%-8d%-10s\n", i + 97, 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);
	}
}

//求哈夫曼编码：循环
void getcode2(hnodetype huffnode[MAXLEAF], int n) {
	int i = 0;
	for (i = 0; i < n; i++) {
		int c = i;//第i个,第一个时c=i，i=1
		int f = 0;//父节点下标
		int j = 0;
		int code[MAXLEAF] = { 0 };//编码数组，记录编码
		int len = 0;
		f = huffnode[c].parent;
		while (f >= 0) {//父节点不为-1的时候
			//printf("%d,%d\n", huffnode[f].weight, huffnode[f].lchild);
			if (huffnode[f].lchild == c)
				code[len++] = 0;
			else
				code[len++] = 1;//记录一下是左孩子还是右孩子
			c = f;//把当前结点变成f
			f = huffnode[c].parent;//f记成f的下一个
		}
		//反向输出数组，即编码
		printf("%-6c%-8d", i + 97, huffnode[i].weight);
		for (j = len - 1; j >= 0; j--)
			printf("%d", code[j]);
		printf("\n");
	}
}

int main(void)
{
	int n = 7;
	printf("输入a~g的权值：");
	hnodetype huffnode[MAXLEAF];
	huffmantree(huffnode, n);
	printf("所有节点权值：");
	output(huffnode, n);
	char dest[MAXLEAF] = "";
	printf("\n递归方法：\n");
	printf("%-6s%-8s%-10s\n", "字符", "权值", "编码");
	getcode1(huffnode, 2 * n - 2, dest, 0);
	printf("\n循环方法：\n");
	printf("%-6s%-8s%-10s\n", "字符", "权值", "编码");
	getcode2(huffnode, n);
	printf("\n");
	return 0;
}

运行结果：