纯C精备，哈夫曼树，考研就业，两者兼得，今日博文，诸君共享。

·
·
·
做任何事情都没有捷径，所谓的捷径，只不过是努力和坚持!

           大家好，我是Cx_330!

前言:

• 今天在一个学习交流群中看到有人发了一道关于离散数学中关于构建最优二叉树并求解哈夫曼编码的问题，我当时看了一下题目，如果用离散数学中的方法去做很快就求解出来了，但是我想给自己增加点难度，并且前段时间学习数据结构的时候也了解过哈夫曼树相关知识，但是之前没有用代码实现，趁着今天是周末，于是自己用出纯c对哈夫曼树的构建以及求解哈夫曼编码的代码实现，

涵盖的知识点

• 二级指针的应用
• 传值/传址的实操
• 数组下标的具体控制实现
• 动态开辟空间的实现

实现思路

• 创建一个结构体数组用来存放结点的信息

• 实现一个二级字符指针(char**)用来存放叶子节点的哈夫曼编码

• 实现一个结构体,包含一个存放(权值)的整形，以及三个指针标志存放左孩子,右孩子,双亲的下标)

• 存放节点的信息要从所索引下标1开始,并且开始的时候将所有结点的双亲,左右孩子的指针标志为0，下标为0的不存放结点信息，否则0将被作为双亲或者左右孩子

必掌握的知识点

• 对于一颗二叉树,若含有n个叶子节点，则总结点的个数为:2*n-1
• 对于哈夫曼的编码,左子树为0，右子树为1

头文件源代码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAXCHAR 100
#define MINWEIGHT 100000
typedef char** HuffmanCode;//二级指针
typedef struct {

	int weight;//权重
	int parent, lchild, rchild;//双亲，左孩子，右孩子

}HTnode, * HuffmanTree;

	//初始化哈夫曼树
	initHuffManTree(HuffmanTree *HF,int n);
	//创建哈夫曼树(类似于顺序表)
	creatHuffManTree(HuffmanTree *HT,int n);
     //(创建哈夫曼编码)
	creatHuffManCode(HuffmanTree HT, HuffmanCode *HC,int n);
	//打印哈夫曼字符
	show_Str(char *str, int n);
	//遍历哈夫曼树
	show_HuffManTree(HuffmanTree HT,int n);
	//遍历哈夫曼编码
	showHuffManCode( HuffmanCode HC, char *str, int n);

main()函数源代码实现

#include"Cx_330.h"
int main()
{
	char str[MAXCHAR];
	HuffmanTree HT;
	HuffmanCode HC;
	int n;
	printf("请输入要编码的字符个数，并输入字符和对应的频数\n");
	scanf("%d",&n);
	initHuffManTree(&HT,n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %c",&HT[i].weight,&str[i-1]);
	}
	creatHuffManTree(&HT,n);
	creatHuffManCode(HT,&HC,n);
	show_Str(str, n);
	show_HuffManTree(HT,n);
	showHuffManCode(HC, str, n);

	return 0;
}

函数实现源代码

#include"Cx_330.h"
void initHuffManTree(HuffmanTree *HT, int n)
{
	int m = 2 * n - 1;
	*HT = (HuffmanTree)malloc((m + 1) * sizeof(HTnode));//创建m+1个HTnode空间是因为让下标从1开始
	for (int i = 1; i <= m; i++) {
		(*HT)[i].parent = 0;
		(*HT)[i].lchild = 0;
		(*HT)[i].rchild = 0;
	}

}

void select(HuffmanTree* HT, int* min_1, int* min_2, int m) {

	int minWeight = MINWEIGHT;
	for (int i = 1; i < m; i++) {
		if ((*HT)[i].weight < minWeight && (*HT)[i].parent == 0) {
			minWeight= (*HT)[i].weight;
			*min_1 = i;
		}
	}
	minWeight = MINWEIGHT;
	for (int i = 1; i < m; i++) {
		if ((*HT)[i].weight < minWeight && (*HT)[i].parent == 0&&i!=(*min_1)) {
			minWeight = (*HT)[i].weight;
			*min_2 = i;
		}
	}
}

void creatHuffManTree(HuffmanTree* HT, int  n) {

	int m = 2 * n - 1;
	int min_1, min_2;
	for (int i = n + 1; i <= m; i++) {

		select(HT,&min_1,&min_2,i);
		(*HT)[min_1].parent = i;
		(*HT)[min_2].parent = i;
		(*HT)[i].lchild = min_1;
		(*HT)[i].rchild = min_2;
		(*HT)[i].weight =(*HT)[min_1].weight+(*HT)[min_2].weight;
	}
}

void creatHuffManCode(HuffmanTree HT, HuffmanCode* HC, int n) {
	(*HC) = (HuffmanCode)malloc((n+1)*sizeof(char*));
	char* ptr = (char*)malloc(n*sizeof(char));
	ptr[n - 1] = '\0';
	int c, f, start;
	for (int i = 1; i <= n; i++) {
		
		start = n - 1;
		c = i;
		f = HT[c].parent;
		while (f != 0) {
			--start;
			if (HT[f].lchild == c) {
				ptr[start] = '0';
			}
			else {
				ptr[start] = '1';
			}
			c = f;
			f = HT[c].parent;
		}
		(*HC)[i] = (char*)malloc(n*sizeof(char));
		strcpy((*HC)[i],&ptr[start]);
	}
	free(ptr);
}

void showHuffManCode(HuffmanCode HC, char* str, int n) {
	char* p = NULL;
	printf("\n-------------------------------------------------\n");

	for (int i = 1; i <= n; i++) {
		printf("[%c] 的哈夫曼编码:", str[i-1]);
		p = HC[i];
		puts(p);
	}
	printf("\n-------------------------------------------------\n");

}

void show_HuffManTree(HuffmanTree HT,int n) {
	printf("-------------------------------------------------\n");
	printf("下标  权重  双亲下标  左孩子下标  右孩子下标\n");
	for (int i = 1; i <= 2*n-1; i++) {
		printf(" [%d]  \t%d  \t%d  \t%d  \t\t%d\n",i,HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
	}
	printf("-------------------------------------------------\n");
}

void show_Str(char* str, int  n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%c ",str[i]);
	}
	printf("\n");
}

结果演示

总结

• 在自己理解完逻辑思路之后自己动手敲一敲，把这个哈夫曼树的构建以及哈夫曼编码的实现完整的实现之后，你就会发现你将会吸收掌握很多新的知识点或者是以前模糊现在记忆更深的知识点，并且对于提高自己的逻辑思维能力和代码实现能力是有很大的帮助的，反正今天我自己通过完整的实现出这个代码之后发现自己对c语言的各种知识点的掌握以及自己的分析逻辑能力有很大的帮助和提高???！