目录

1.哈夫曼树结构

2.构造一个n个叶子结点的二叉树

3.select函数的实现

4.打印哈夫曼树

5.哈夫曼编码

6.根据哈夫曼树求哈夫曼编码

1.哈夫曼树结构

创建哈夫曼树结构体，我们额外添加了个character存储权值对应的字符

//哈夫曼树储存表示
typedef struct{
	char character;//结点的字符
	int weight;//结点的权值
	int parent, lchild, rchild;//结点的双亲、左孩子、右孩子
}HTNode, *HuffmanTree;

2.构造一个n个叶子结点的二叉树 

因为第0号单元未使用，所以根据传入的n开辟n+1个空间，传入二级指针以便改变一级指针。

void CreateHuffmanTree(HuffmanTree* HT, int n) {
	if (n <= 1)
		return;
	int i = 0;
	int m = 2 * n - 1;//m为所有结点个数
	
	//因为从1号结点开始使用，0号结点未使用，所以开辟m+1个结点的空间
	HuffmanTree ptr = (HuffmanTree)malloc(sizeof(HTNode) * (m + 1));
	if (ptr == NULL)//开辟空间失败返回
	{
		perror("CreateHuffmanTree");
		return;
	}
	*HT = ptr;//改变指针HT
	//把1~m号结点中左孩子、右孩子、双亲下标初始化为0，字符初始化为空格
	for ( i = 1; i <= m; i++)
	{
		(ptr + i)->lchild = 0;
		(ptr + i)->rchild = 0;
		(ptr + i)->parent = 0;
		(ptr + i)->character = ' ';
	}
	//输入前n个叶子结点的权值
	printf("输入%d个叶子结点的字符和权值n", n);
	for ( i = 1; i <= n; i++)
	{
		getchar();
		scanf("%c", &((ptr + i)->character));
		scanf("%d", &((ptr + i)->weight));
	}
	//开始创建哈夫曼树
	for ( i = n + 1; i <= m; i++)
	{
		int s1, s2;
		Select(ptr, i - 1, &s1, &s2);//在第1到第i-1个数中找权值最小的两个结点
		(ptr + i)->lchild = s1;//结点i的左孩子为s1
		(ptr + i)->rchild = s2;//结点i的右孩子为s2
		(ptr + i)->weight = (ptr + s1)->weight + (ptr + s2)->weight;//结点i的权值为s1和s2的权值之和
		//结点s1和s2的双亲改为i;
		(ptr + s1)->parent = i;
		(ptr + s2)->parent = i;
	}
}

3.select函数的实现

在构造哈夫曼树时，用于找到前n项两个最小值，返回两个最小权值的结点

void Select(HuffmanTree HT, int n, int* s1, int* s2) {
	int i = 0;
	//把第1个双亲域为0的值的结点赋给s1
	for (i = 1; i <= n; i++)
	{
		//如果双亲不为0，则跳过本次循环
		if ((HT + i)->parent == 0) {
			*s1 = i;
			break;
		}
	}
	//找到权值最小的下标
	for (i = 0; i <= n; i++)
	{
		if (((HT + i)->weight) < (HT + *s1)->weight)
			if ((HT + i)->parent == 0)
				*s1 = i;//如果s1结点的权值大于i结点的权值，更新s1
	}
	//把第2个双亲域为0的值的结点赋给s1,避免第一个就是权值最小的结点，和s1重复
	for (i = 1; i <= n; i++)
	{
		//如果双亲不为0，或为s1所在的最小值，则跳过本次循环
		if (((HT + i)->parent == 0) && (i != *s1)) {
			*s2 = i;//s2赋为第一个不为s1的结点
			break;
		}
	}
	//找到除去s1结点权值最小的下标
	for (i = 0; i <= n; i++)
	{
		if (i == *s1)
			continue;
		if (((HT + i)->weight) < (HT + *s2)->weight)
			if ((HT + i)->parent == 0) {
				*s2 = i;//如果s2结点的权值大于i结点的权值，更新s2
			}
	}
}

4.打印哈夫曼树

为方便验证按结点顺序打印哈夫曼树

void print(HuffmanTree HT, int n) {
	int m = 2 * n - 1;
	printf("字符   权值   双亲   左孩子   右孩子n");
	for (int i = 1; i <= m; i++)
	{
		printf("%ct%dt%dt%dt%dn",(HT + i)->character, (HT + i)->weight, (HT + i)->parent, (HT + i)->lchild, (HT + i)->rchild);
	}
}

测试：

int main() {
	HuffmanTree HT;
	int n;
	printf("输入叶子结点个数:>");
	scanf("%d", &n);
	CreateHuffmanTree(&HT, n);//建立8个叶子结点的二叉树
	print(HT, n);//打印验证
    return 0;
}

运行结果：

5.哈夫曼编码

typedef char** HuffmanCode;//动态分配数组存储哈夫曼编码表

6.根据哈夫曼树求哈夫曼编码

void CreatHuffmanCode(HuffmanTree HT, HuffmanCode* HC, int n) {
	int start, c, f;
	HuffmanCode ptr = (HuffmanCode)malloc(sizeof(char*)*(n+1));//分配n个字符的头指针矢量
	if (ptr == NULL)//分配失败报错并返回
	{
		perror("CreatHuffmanCode");
		return;
	}
	*HC = ptr;//更新指针HC
	char* cd = (char*)malloc(sizeof(char) * n);//分配临时空间存放编码
	cd[n - 1] = '';//最后一个位置放入字符串结束标志
	for (int i = 1; i <= n; i++)
	{
		char* tmp = cd + n - 1;//保存此时存储位置
		start = n - 1;
		c = i;
		f = HT[i].parent;
		while (f != 0)
		{
			start--;
			if (HT[f].lchild == c)//如果i结点为f结点的左孩子，把0存如数组
				cd[start] = '0';
			else//如果i结点为f结点的右孩子，把1存入数组
				cd[start] = '1';
			tmp--;//更新此时存储位置
			c = f;
			f = HT[f].parent;
		}
		ptr[i] = (char*)malloc(sizeof(char) * (n - start));//分配n-start个空间
		strcpy(ptr[i],tmp);//将求得编码复制进ptr中
	}
	free(cd);//释放cd位置空间
	cd = NULL;//置为空指针
}

测试：

int main() {
	HuffmanTree HT;
	HuffmanCode HC;
	int n;
	printf("输入叶子结点个数:>");
	scanf("%d", &n);
	CreateHuffmanTree(&HT, n);//建立8个叶子结点的二叉树
	print(HT, n);
	CreatHuffmanCode(HT, &HC, n);
	for (int i = 1; i <= n; i++)
	{
		printf("n");
		printf(HC[i]);
	}
	return 0;
}

运行结果：