哈夫曼树

程序员文章站 2022-03-23 09:19:36

...

哈夫曼树(C语言简单实现）

本文参考自《大话数据结构》，至于原理图那些，这里就不赘述了，网上很多，自己找。下面做了简单代码实现，代码依然存在较多缺陷，但是基本可运行，不喜勿喷，有改进和建议欢迎评论区评价。

树的路径长度就是从树根到每一结点的路径长度之和。

结点的带权的路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和。假设有n个权值{w1,w2,…,wn}，构造一棵有n个叶子结点的二叉树，每个叶子结点带权wk，每个叶子的路径长度为1k，我们通常记作WLP，其中带权路径长度WLP最小的二叉树称为哈夫曼树(最优二叉树) 。

哈夫曼算法描述

根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti中只有一个带权为wi根结点，其左右子树均为空；
在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和；
在F中删除这两棵树，同时将新得到的二叉树加入F中；
重复2和3步骤，直到F只含一棵树为止。这棵树就是哈夫曼树。

哈夫曼编码

将左孩子编码为0，右孩子编码为1。

编码中非0即1，若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码称为前缀编码 。

编码和解码都要用到哈夫曼树，否则解不出码。

一般地，设需要编码的字符集为{d1,d2,…,dn}，各个字符在电文中出现的次数或频率集合为{w1,w2,…,wn}，以d1,d2,…,dn作为叶子结点，以w1,w2,…,wn作为相应叶子结点的权值来构造一棵哈夫曼树。规定哈夫曼的左分支代表0，右分支代表1，则从根结点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，这就是哈夫曼编码。

算法分析

主要就是在构建哈夫曼树的时候，分了4种情况：

生成3个新结点：父结点，左右孩子结点；
生成2个结点：父结点和左孩子或者父结点和右孩子；
不生成结点，直接链接结点；

另一个就是编码的时候，采用的是二叉树遍历+栈的先进后出机制来存储0和1编码。

最后一个就是这份代码还有很多可以优化的地方，比如：

构建树的时候4种情况里，可以把出现情况比较多的放前面，减少判断的次数；
左右孩子大小问题；
构建树的过程比较复杂，可以优化；
设定的哈夫曼树结构复杂，可以拆分等…

简单实现

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

typedef char TElemType;	//数据域类型 

/* 栈 */
struct StackNode{
	char chs;
	StackNode* next;
};

struct Stack{
	StackNode* top;
	int count;
};

//声明一个全局栈，用来存储编码 
Stack* s = (Stack*)malloc(sizeof(Stack));

struct HaffmanNode{
	TElemType data;	//数据域 
	int weight;	//权重
	HaffmanNode *lchild, *rchild;	//左右孩子 
	//编码值，因为main函数里设置的字符串s长度为20
	char code[10];
	int born;	//标志，该结点是不是生成的
	int codeLength;
};

/* 出栈 */
void pop(){
	if(s->count != 0){
		StackNode* temp = (StackNode*)malloc(sizeof(StackNode));
		temp = s->top;
		s->top = temp->next;
		free(temp);
		s->count--;
	}
}

/* 入栈 */
void push(char ch){
	StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
	newNode->chs = ch;
	newNode->next = s->top;
	s->top = newNode;
	s->count++;
} 

/* 交换函数 */
void swap(HaffmanNode* haffman, int i, int j){
	HaffmanNode temp;
	temp.data = haffman[i].data;
	temp.weight = haffman[i].weight;
	temp.born = haffman[i].born;
	temp.lchild = haffman[i].lchild;
	
	haffman[i].data = haffman[j].data;
	haffman[i].weight = haffman[j].weight;
	haffman[i].born  =haffman[j].born;
	haffman[i].lchild = haffman[j].lchild;
	
	haffman[j].data = temp.data;
	haffman[j].weight = temp.weight;
	haffman[j].born = temp.born;
	haffman[j].lchild = temp.lchild;
}

/* 排序 */
void sort(HaffmanNode* haffman, int haffmanLength){
	//因为待排序数据不多，所以这里用选择排序，时间复杂度为O(n^2)，得到的序列为从大到小，可以根据需求修改 
	int i, max, j;
	for(i=0;i<haffmanLength;i++){
		max = i;
		for(j=i+1;j<=haffmanLength;j++){
			if(haffman[max].weight < haffman[j].weight)
				max = j;
		}
		if(max != i)
			swap(haffman, i, max);
	}
}

/* 哈夫曼编码过程，相当于遍历，这里采用二叉树中序遍历 */
void coding(HaffmanNode* h){
	int i;
	if(h){	//如果该结点不为空

		push('0');	//左分支给0
		coding(h->lchild);
		pop();		//编码完要出栈 
		
		//遍历栈得到编码 
		StackNode* p = s->top;
		for(i=s->count-1;i>=0;i--){
			h->code[i] = p->chs;
			p = p->next;		
		}
		//编码长度 
		h->codeLength = s->count;
		push('1');	//右分支给1 
		coding(h->rchild);
		pop();		//又分支同上 
	}
}

/* 遍历打印，这里采用前序遍历 */
void print(HaffmanNode* h){
	int i;
	if(h){
		if(h->born == 0){	//是原结点，非生成的 
			printf("%c:",h->data);
				for(i=0;i<h->codeLength;i++)
					printf("%c",h->code[i]);
			printf("\n");
		}
		print(h->lchild);
		print(h->rchild);
	}
}

/* 构建哈夫曼树 */
HaffmanNode* InitHaffmanTree(HaffmanNode* haffman, int haffmanNodeLength){
	while(haffmanNodeLength--){	//次数，比长度少1
		//每次都会新生成一个父结点
		HaffmanNode* newNode = (HaffmanNode*)malloc(sizeof(HaffmanNode));
		//如果2个结点都是新的
		if(!haffman[haffmanNodeLength].born && !haffman[haffmanNodeLength+1].born){
			//生成左右孩子
			HaffmanNode* lChild = (HaffmanNode*)malloc(sizeof(HaffmanNode));
			HaffmanNode* rChild = (HaffmanNode*)malloc(sizeof(HaffmanNode));
			lChild->born = rChild->born = 0;	//标记结点为计算生成的，而不是原生的
			//左孩子 
			lChild->data = haffman[haffmanNodeLength].data;
			lChild->weight = haffman[haffmanNodeLength].weight;
			lChild->born = haffman[haffmanNodeLength].born;
			lChild->lchild = lChild->rchild = NULL;
			//右孩子
			rChild->data = haffman[haffmanNodeLength+1].data;
			rChild->weight = haffman[haffmanNodeLength+1].weight;
			rChild->born = haffman[haffmanNodeLength+1].born;
			rChild->lchild = rChild->rchild = NULL;
			//新的父结点只需存权值和孩子的地址 
			newNode->lchild = lChild;
			newNode->rchild = rChild;
		}else if(haffman[haffmanNodeLength].born && haffman[haffmanNodeLength+1].born){
			//如果2个结点都是生成的，那么连接起来
			newNode->lchild = haffman[haffmanNodeLength].lchild;
			newNode->rchild = haffman[haffmanNodeLength+1].lchild;
		}else if(!haffman[haffmanNodeLength].born && haffman[haffmanNodeLength+1].born){
			//新生成一个左孩子
			HaffmanNode* lChild = (HaffmanNode*)malloc(sizeof(HaffmanNode));
			//左孩子设置
			lChild->data = haffman[haffmanNodeLength].data;
			lChild->weight = haffman[haffmanNodeLength].weight;
			lChild->lchild = lChild->rchild = NULL;
			lChild->born = haffman[haffmanNodeLength].born;
			//父节点设置 
			newNode->lchild = lChild;
			newNode->rchild = haffman[haffmanNodeLength+1].lchild;
		}else{
			//新生成一个右孩子 
			HaffmanNode* rChild = (HaffmanNode*)malloc(sizeof(HaffmanNode));
			//右孩子设置
			rChild->data = haffman[haffmanNodeLength+1].data;
			rChild->weight = haffman[haffmanNodeLength+1].weight;
			rChild->lchild = rChild->rchild = NULL;
			rChild->born = haffman[haffmanNodeLength+1].born;
			//父节点设置 
			newNode->rchild = rChild;
			newNode->lchild = haffman[haffmanNodeLength].lchild;
		}
		//父节点的权值计算和born设置，每次都是一样的操作，也提取出来
		newNode->born = 1;
		newNode->weight = haffman[haffmanNodeLength].weight + haffman[haffmanNodeLength+1].weight;
		//赋给数组，用于排序
		haffman[haffmanNodeLength].born = newNode->born;
		haffman[haffmanNodeLength].weight = newNode->weight;
		haffman[haffmanNodeLength].lchild = newNode;	//数组里的左孩子暂时用来存储新父结点地址
		//重新排序 
		sort(haffman, haffmanNodeLength);
	}
	//此时树已经构建好了，接下来就是编码过程，相当于遍历的过程，这里采用前序遍历 
	//此时，haffman数组的haffman[0].lchild存的就是哈夫曼树根结点的地址， 
	//haffman[0].weight存的就是哈夫曼树的权值
	//结束之后，我们要将haffman赋值为lchild，因为只是用来暂存，所以这里需要修改为原左孩子的地址，切记，很重要
	haffman = haffman->lchild;
	coding(haffman);
	return haffman;
}

int main(){
	//栈初始化 
	s->count = 0;
	s->top = NULL;
	//输入字符串
	char s[20];
	HaffmanNode haffmanNode[20];	//哈夫曼结点20个，用来暂存字符串相关信息 
	gets(s);
	//统计各结点个数
	int i, j, haffmanNodeLength;
	//朴素匹配算法 
	for(i=0, j, haffmanNodeLength=0;i<strlen(s);i++){
		for(j=0;j<haffmanNodeLength;j++){
			if(s[i] == haffmanNode[j].data){
				//如果字符相等 
				haffmanNode[j].weight++;	//权重加1
				break;
			}
		}
		if(j >= haffmanNodeLength){
			haffmanNode[haffmanNodeLength].data = s[i];	//否则增加字符到哈夫曼数组里，并且设置权值为1 
			haffmanNode[haffmanNodeLength].weight = 1;
			haffmanNode[haffmanNodeLength].born = 0;	//结点非生成的 
			haffmanNodeLength++;
		}
	}
	//减掉最后的+1 
	haffmanNodeLength--;
	//排序
	sort(haffmanNode, haffmanNodeLength);
	//初始化和编码哈夫曼树 
	HaffmanNode* haffman = InitHaffmanTree(haffmanNode, haffmanNodeLength);
	print(haffman);
	return 0;
}

最终结果

输入一段20个字符以内的字符串，输出哈夫曼编码

哈夫曼树

相关标签：数据结构 C 数据结构

上一篇：【C语言】【数据结构】循环队列的基本操作（创建、入队、出队、队长、队头、遍历、应用）

下一篇：选择排序

哈夫曼树

哈夫曼树(C语言简单实现）

哈夫曼算法描述

哈夫曼编码

算法分析

简单实现

最终结果

三星牌哈曼卡顿条形音响发布：7.1.4杜比全景声

【数据结构与算法】二叉树——哈夫曼编码

哈夫曼树的构建（C语言）

哈夫曼编码的理解(Huffman Coding)

第三次哈尔科夫战役德详细经过是怎样的？最后谁赢了

哈尔科夫反击战的起因是什么？是在什么背景下发生的

BZOJ4198: [Noi2015]荷马史诗(哈夫曼树)

全球蓝牙音箱品牌哪个好：索爱、马歇尔、哈曼卡顿纷纷上榜

js神秘的电报密码哈弗曼编码实现

哈曼卡顿加持雷军预热小米10S：小米有史以来音质最好的手机

哈夫曼树

哈夫曼树(C语言简单实现）

哈夫曼算法描述

哈夫曼编码

算法分析

简单实现

最终结果

三星牌哈曼卡顿条形音响发布：7.1.4杜比全景声

【数据结构与算法】二叉树——哈夫曼编码

哈夫曼树的构建（C语言）

哈夫曼编码的理解(Huffman Coding)

第三次哈尔科夫战役德详细经过是怎样的？最后谁赢了

哈尔科夫反击战的起因是什么？是在什么背景下发生的

BZOJ4198: [Noi2015]荷马史诗(哈夫曼树)

全球蓝牙音箱品牌哪个好：索爱、马歇尔、哈曼卡顿纷纷上榜

js神秘的电报密码 哈弗曼编码实现

哈曼卡顿加持 雷军预热小米10S：小米有史以来音质最好的手机

js神秘的电报密码哈弗曼编码实现

哈曼卡顿加持雷军预热小米10S：小米有史以来音质最好的手机