数据结构18————哈夫曼树

一.内容

1. 哈夫曼树的定义和原理
2. 哈夫曼树的建立
3. 哈夫曼编码
4. 哈夫曼算法的实现

二.哈夫曼树的定义和原理

1.哈夫曼树的定义及作用

哈夫曼树的又称为最优二叉树,是带权路径最短的树，可用来构造最优编码，常用于数据压缩和信息传递

2.哈夫曼树的相关概念

• 路径:从一个结点到另一个结点之间的分支路径
• 路径长度:从一个结点到另一结点所经过的分支数目
• 结点的权值:树中每个结点所赋予的具有某种实际意义的实数
• 带权路径长度:从树根到某一结点的路径长度与该结点的权的乘积。
• 树的带权路径长度(WPL):树中从根到所有叶子结点的各个带权路径长度之和。

如图所示的树,其WPL=7x4+9x4+5x3+4x2+2x1=89

所以哈夫曼树就是,相同叶子结点所构成的树中，WPL最小的一颗。

三.哈夫曼树的建立

如果给定叶子节点的权值，如何构造出一颗WPL最小的树呢？这个过程就是构造哈夫曼树的过程

1.思想

每次选择节点集合中最小的两个节点，构成一颗树,根节点的权值为两个之和，将根节点加入节点集合，重复上述过程。
形式化表述

1.根据给定的n个权值{w1,w2……wn},构造出n颗二叉树的集合F={T1.T2……Tn},其中每一棵二叉树均只含一个带权值为wi的根节点，其左右子树为空树
2.在F中选择其根节点为权值最小的两颗二叉树，分别作为左右子树构造出一颗新的二叉树。并置这颗新树根节点权值为左右根节点的权值之和。
3.在F中删去这两棵树，同时加入新生成的树
4.重复23过程，直到F中只剩一颗树为止。

2.例子

3.如何存储

哈夫曼树的存储可以使用三叉链表和静态三叉链表，为了简单考虑，一般选择静态三叉链表来实现哈夫曼树的存储

4.静态三叉链表实现二叉树的存储

四.哈夫曼编码

我们前文说过，哈夫曼树主要应用是在数据压缩信息传递中，而如何应用哈夫曼树进行数据的压缩，这就涉及到哈夫曼树编码。

1.编码

编码是什么?
举个例子如果我们需要通过网络传输一段文字；ABCDEFGH，那么很容易想到，让A=000，B=001,C=010,D=011,F=100,G=101,H=111。所以ABCDEFG就可以表示为000.001.010.011.100.101.110.111。通过这个规则，就可以表示ABCDEFG所构成的任意一段文字。文字转换出的二进制就是编码。

上面的编码可以解决大部分的问题，但是否可以进行更好的优化，比如让它编码后的二进制长度尽可能的达到更小。

如何达到呢？我们可以通过让出现频率大的编码尽可能的短，出现概率小的编码啊可以适当的长点。但是存在一个问题，比如说AB出现的频率大，让A=0，B=1，C出现的频率小，让C=01。那么问题来了，01代表AB还是代表C。所以如果要设计长度不等的编码必须满足

任何一个字符编码都不是另一个字符的编码的前缀，这种编码就是前缀编码

2.哈夫曼编码

哈夫曼编码就是一种前缀编码,而且是编码后最短的前缀编码。
哈夫曼树的构建

将每个字符出现的次数作为权值，按照哈夫曼树的构建过程组成的一颗二叉树

哈夫曼编码

从哈夫曼树的根节点出发，左子树输出0，右子树输出1。知道达到叶子节点后停止，此时输出的二进制就是该叶子节点的哈夫曼编码

3.例子

五.哈夫曼算法

我的代码设计未舍弃下标为0的位置，所以叶子节点从0开始

1.结构体的设计

#include <stdio.h>
#define N 30
#define M 2*N-1
typedef struct{
	int weight;
	char data; 
	int parent,Lchild,Rchild;
}HTNode,HuffmanTree[M+1];

2.哈夫曼树的建立

void CrtHuffmanTree(HuffmanTree	ht,int n){ //创建哈夫曼树 
	int m=2*n-1;
	int i;
	int s1,s2;
	for(i=0;i<n;i++){       //初始化叶子节点 
		scanf("%d",&ht[i].weight);
		ht[i].data = 'A'+i; 
		ht[i].parent=-1;
		ht[i].Lchild=-1;
		ht[i].Rchild=-1; 
	}	
	for(i=n;i<m;i++){   //初始化非叶子节点
		ht[i].weight=0;
		ht[i].parent=-1;
		ht[i].Lchild=-1;
		ht[i].Rchild=-1; 
	}
	
	for(i=n;i<m;i++) //创建哈夫曼树
	{
		seek(ht,i,&s1,&s2);	 //寻找ht中i之前最小的两个元素下标，s1<s2; 
		ht[s1].parent=i; 
		ht[s2].parent=i;
		ht[i].weight = ht[s1].weight+ht[s2].weight;
		ht[i].Lchild = s1;
		ht[i].Rchild = s2;
	}

}

void seek(HuffmanTree ht,int n,int *s1,int *s2){  //寻找ht中i之前最小的两个元素下标，s1<s2; 
	int i,j;
	for(i=0;i<n&&ht[i].parent!=-1;i++); //s1,s2的初始化 
	j=i;
	i++;
	for(;i<n&&ht[i].parent!=-1;i++);
	*s1 = ht[i].weight<ht[j].weight?i:j;
	*s2 = ht[i].weight<ht[j].weight?j:i;
	i++;
	while(i<n){
		if(ht[i].parent!=-1){
			
		}else if(ht[i].weight<ht[*s1].weight){
			*s2 = *s1;
			*s1 = i;
		}else if(ht[i].weight<ht[*s2].weight){
			*s2 = i;
			
		}
		i++; 
	}
}

3.输出所有字符的编码

void codinghuffman(HuffmanTree	ht,int n){ //编码所有的叶子节点 
	int i,j;
	char str[N];
	int p,q; //p当前节点，q是p的双亲节点 
	for(i=0;i<n;i++){
		p=i;
		for(j=0;ht[p].parent!=-1;j++){     
			
			q=ht[p].parent;
			if(p==ht[q].Lchild){ //如果是左节点,则为0 
				str[j]='0';
			}else{           //如果是右节点,则为1 
				str[j]='1';
			}
			p=ht[p].parent;
		}
		
		printf("%c:",ht[i].data); //打印结果 
		for(j=j-1;j>=0;j--){
			printf("%c",str[j],j);
		}
		printf("\n");
	}
} 

4.编码字符串

void aCodinghuffman(HuffmanTree	ht){ //编码字符串 
	int i,j;
	char in[N];
	char str[N];
	int p,q;
	getchar();
	gets(in);	
	for(i=0;in[i];i++){ //遍历每个字母 
		p=in[i]-'A'; //确定该叶子节点存储的位置,这句根据具体问题而定 
		for(j=0;ht[p].parent!=-1;j++){    //解码每个字母 
			
			q=ht[p].parent;
			if(p==ht[q].Lchild){ //如果是左孩子 
				str[j]='0';
			}else{            //如果是右孩子 
				str[j]='1';
			}
			p=ht[p].parent;
		} 
		for(j=j-1;j>=0;j--){  //打印结果 
			printf("%c",str[j],j);
		}
	}
	printf("\n");
} 

5.译码

void decodeHuffmanTree(HuffmanTree ht,int n){ //译码 
	int i,j;
	char str[N];
	int p=2*n-2; // p当前节点，p当前节点儿子
	 
	gets(str);
	for(i=0;str[i];i++){
		if(str[i]=='1'){
			p = ht[p].Rchild;
		}else if(str[i]=='0'){
			p = ht[p].Lchild;
		}
		if(ht[p].Lchild==-1&&ht[p].Rchild==-1){  //当前字段解码完毕 
			printf("%c",ht[p].data);
			p =2*n-2; 
		}
	} 
} 

6.带权路径长(WPL)

int WPL(HuffmanTree ht,int n){
	int wpl=0;
	int h;
	int p;
	int i;
	for(i=0;i<n;i++){
		h=0;
		for(p=i;ht[p].parent!=-1;p=ht[p].parent){
			h++;
		}
		wpl = wpl+ h*ht[i].weight;
	}
	return wpl;
}

六.源代码

text15中

七.参考资料

《大话数据结构》
《数据结构与算法分析》