数据结构与算法精解：哈夫曼树及其哈夫曼编码

哈夫曼树是什么？

哈夫曼树（Huffman Tree）是一种特殊的二叉树，由David A. Huffman在1952年发明的，用于数据压缩领域。哈夫曼树是一种最优的二叉树，因为它具有最小的加权路径长度。这里的“最优”是指在给定的一组权重（通常是字符出现频率）下，哈夫曼树的加权路径长度（即树中所有叶节点的权重乘以其到根节点的距离）是最小的，以下是哈夫曼树的特点：

1.完全二叉树：除了最后一层外，每一层都是满的

2.加权路径长度最小：所有叶节点的权重乘以其到根节点的距离之和是最小的

3.每个节点都有权重：叶节点代表单个字符，非叶节点代表字符的集合

哈夫曼编码是什么？

哈夫曼编码是一种使用哈夫曼树进行编码的方法。它将每个字符映射为一个唯一的二进制串，这些二进制串的长度不同，且是根据字符出现频率来确定的。频率越高的字符，其编码越短；频率越低的字符，其编码越长。这种编码方式可以有效地减少数据的存储空间或传输时间。实现哈夫曼编码的步骤如下：

1.统计字符频率：首先统计数据集中每个字符出现的频率

2.构建哈夫曼树：

1.将每个字符及其频率作为叶子节点放入优先队列（通常是最小堆）

2.从队列中取出两个权重最小的节点，创建一个新的内部节点，其权重为这两个节点权重之和

3.将新节点重新加入队列。重复上述步骤，直到队列中只剩下一个节点，这个节点就是哈夫曼树的根节点

3.生成编码：从根节点开始，向左子树走标记为0，向右子树走标记为1，直到到达叶节点，此时叶节点对应的字符的路径标记就是其哈夫曼编码

哈夫曼编码的应用

哈夫曼编码是一种非常实用的编码技术，它通过利用数据的内在特性来优化存储和传输效率：

1.数据压缩：用于无损数据压缩，特别是在文本压缩中非常有效。

2.文件压缩：如ZIP文件格式就使用了哈夫曼编码。

3.通信协议：在某些通信协议中，用于减少传输数据的大小。

包含头文件

cpp

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

结点设计

cpp

#define Initsize 100typedef int Elemtype;int Node[Initsize][2];				//定义二维数组Node存储输入的字符和字符所含的权值int NodeValue[Initsize];			//定义一维数组NodeValue存储经排序过的字符的权值int Hand = 0;						//定义整形变量Hand作为数组NodeValue的头指针int CodeHead = 0;					//定义int类型变量CodeHead作为指针数组Code的头指针typedef struct HTree {	Elemtype value;					//存储结点权值	Elemtype Lvalue, Rvalue;		//存储孩子标识	struct HTree* lchild;			//存储左孩子树	struct HTree* rchild;			//存储右孩子树}HTree,*HfmTree;HfmTree Head;						//定义全局变量Head作为哈夫曼树的根节点指针HfmTree Code[Initsize];				//定义HTree类型的指针数组Code，存储结点的地址

接口函数定义

cpp

void InitHTree(HfmTree& A);		//用于初始化哈夫曼树void InsertNode(int A);			//用于输入字符和其权值void SortNodeV(int A);			//用于对输入的权值进行排序void InitLHfm(HfmTree& A);		//用于哈夫曼树的左子树进行初始化并赋值void InitRHfm(HfmTree& A);		//用于哈夫曼树的右子树进行初始化并赋值void InsertHTree(HfmTree& A,int B); //用于创建哈夫曼树void PostOrder(HfmTree A);	        //用于对哈夫曼树进行后序遍历void InputBTree(HfmTree A);	        //用于对哈夫曼树的结点权值输出void SeekHTreeL(HfmTree A, int B);	//用于单独寻找哈夫曼树的左子树的字符及权值void SeekHTreeR(HfmTree A, int B);	//用于寻找哈夫曼树的右子树的字符及权值void InputHfmCode(HfmTree A,int B);	//用于输出哈夫曼编码void InitRootHfm(HfmTree& A,HfmTree &B,HfmTree &C); //用于对哈夫曼树的根结点进行初始化并赋值

接口函数实现

cpp

void InputHfmCode(HfmTree A,int B) { //用于输出哈夫曼编码	int i,j;	while (A != NULL) {				 //对哈夫曼树的左子树进行进栈操作		Code[CodeHead] = A;		A = A->lchild;		CodeHead++;	}	printf("\n");	SeekHTreeL(A, B);		//使用函数SeekHtreeL对其哈夫曼树进行寻找左子树的字符及权值	for (i = 1; i < CodeHead; i++) {		printf("%d", Code[i]->Lvalue);	        //对栈里结点所含的Lvalue进行输出(从根结点开始输出其含有的LvaLue)	}	CodeHead--;					//出栈操作	while (CodeHead != 0) {		//判断栈是否为空		printf("\n");		SeekHTreeR(A, B);		//使用函数SeekHTreeR对其哈夫曼树进行寻找右子树的字符及权值		for (i = 0; i <= CodeHead - 1; i++) {	        //对栈里结点所含的Lvalue进行输出(从根结点开始输出其含有的LvaLue)			if (i == CodeHead - 1) {				//若为栈尾结点则输出其右子树				printf("%d", Code[i]->Rvalue);					break;			}			printf("%d", Code[i]->Lvalue);		}		CodeHead--;				//出栈操作	}}void SeekHTreeR(HfmTree A, int B) {	//用于寻找哈夫曼树的右子树的字符及权值	int i,j;	for (i = CodeHead - 1; i >= 0; i++){ //遍历栈		if (i == CodeHead-1) {			 //判断是否为栈的倒数第二个结点(跟定义的结点的有关)			for (j = 0; j < B; j++)	{	 //遍历存储字符及权值的数组，寻找对应的字符和权值				if (Node[j][1] == Code[i]->rchild->value) {					Node[j][1] = -1;	                    //未防止字符不一样，但权值相同的出现，造成输出哈夫曼编码错误					printf("%c的哈夫曼编码为：", Node[j][0]);					break;									}			}		}		break;				}}void SeekHTreeL(HfmTree A, int B){	//用于单独寻找哈夫曼树的左子树的字符及权值	int i,j;	for (i = 0; i < CodeHead; i++) {	//遍历栈		if (i == CodeHead - 1) {		//判断是否为栈的倒数第二个结点(跟定义的结点的有关)			for (j = 0; j < B; j++) {	//遍历存储字符及权值的数组，寻找对应的字符和权值				if (Node[j][1] == Code[i]->value) {						Node[j][1] = -1;	                    //未防止字符不一样，但权值相同的出现，造成输出哈夫曼编码错误					printf("%c的哈夫曼编码为：", Node[j][0]);					break;				}			}		}	}}void InputBTree(HfmTree A) {	//用于对哈夫曼树的结点权值输出			printf("%d   ", A->value);}void PostOrder(HfmTree A) {		//用于对哈夫曼树进行后序遍历			if (A != NULL) {		PostOrder(A->lchild);			PostOrder(A->rchild);			InputBTree(A);				}}void InsertHTree(HfmTree& A,int B) {//用于创建哈夫曼树	if(Hand<B-1){				//判断是否已将所有字符及权值进行构建对应的哈夫曼树的结点		if (A == NULL) {					HfmTree Q = (HTree*)malloc(sizeof(HTree));					HfmTree W = (HTree*)malloc(sizeof(HTree));					InitLHfm(Q);				//使用函数InitLHfm对其左子树初始化			Hand++;			InitRHfm(W);				//使用函数InitRHfm对其右子树初始化			InitRootHfm(A, Q, W);		//使用函数InitRootHfm对其根结点初始化			Head = A;					//更新哈夫曼树的头指针的指向			InsertHTree(A, B);					}		else {			HfmTree Q = (HTree*)malloc(sizeof(HTree));					HfmTree W = (HTree*)malloc(sizeof(HTree));					Hand++;			InitRHfm(Q);				//使用函数InitRHfm对其右子树初始化			InitRootHfm(W, A, Q);		//使用函数InitRootHfm对其根结点初始化			Head = W;			InsertHTree(W, B);		}	}}void InitRootHfm(HfmTree& A, HfmTree& B, HfmTree& C) {    //用于对哈夫曼树的根结点进行初始化并赋值	A = (HTree*)malloc(sizeof(HTree));	A->value = B->value + C->value;			//根结点的权值为两个子结点的权值之和	A->Lvalue = 1;							//添加左子树标识	A->Rvalue = 0;	A->lchild = B;							//添加根结点指向的左子树	A->rchild = C;							//添加根结点指向的右子树	printf("新建的根结点的权值数据为%d\n", A->value);}void InitRHfm(HfmTree& A) {		//用于哈夫曼树的右子树进行初始化并赋值	A->value = NodeValue[Hand];	//对结点所含的权值进行更新	A->Lvalue = 0;	A->Rvalue = 1;				//添加右子树标识	A->lchild = NULL;							A->rchild = NULL;	printf("新建的右孩子的权值数据为%d\n", A->value);}void InitLHfm(HfmTree& A) {			//用于哈夫曼树的左子树进行初始化并赋值	A->value = NodeValue[Hand];		//对结点所含的权值进行更新	A->Lvalue = 1;					//添加左子树标识	A->Rvalue = 0;	A->lchild = NULL;	A->rchild = NULL;	printf("新建的左孩子的权值数据为%d\n", A->value);}void SortNodeV(int A) {				//用于对输入的权值进行排序	int i, j, Q;	for (i = 0; i < A - 1; i++) {				//冒泡排序		for (j = 0; j < A - 1 - i; j++)			if (NodeValue[j] > NodeValue[j + 1]) {				Q = NodeValue[j];				NodeValue[j] = NodeValue[j + 1];				NodeValue[j + 1] = Q;			}	}}void InsertNode(int A) {			//用于输入字符和其权值	int i, j;	char Q;	for (i = 0; i < A; i++) {		j = 0;		printf("请输入结点的字符");		getchar();			//清除缓冲区，防止赋值脏数据		Q=getchar();		Node[i][j] = (int) Q;		j++;		printf("请输入结点的权值");		scanf_s("%d", &Node[i][j]);		NodeValue[i] = Node[i][j];	}}void InitHTree(HfmTree& A) {		//用于初始化哈夫曼树	A = NULL;	printf("初始化哈夫曼树成功\n");}

哈夫曼编码测试案列

cpp

void main() {	int NodeSize,i;	HfmTree X;	InitHTree(X);	printf("请问需要输入多少个字符");	scanf_s("%d", &NodeSize);	InsertNode(NodeSize);	SortNodeV(NodeSize);	InsertHTree(X, NodeSize);	printf("创建哈夫曼树成功\n");	printf("后序遍历的哈夫曼树为：");	PostOrder(Head);	printf("\n");	InputHfmCode(Head,NodeSize);}