数据结构–哈夫曼树

最新发布博客：算法设计与分析-分治篇 

zhttps://blog.csdn.net/XUN__MLF/article/details/134620313?spm=1001.2014.3001.5502

哈夫曼树及其应用

1、哈夫曼树的基本概念

• 路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径

• 结点的路径长度：两结点间路径上的分支数。

• 树的路径长度：从树根到每一个结点的路径长度之和。记作TL

• 结点树目相同的二叉树中，完全二叉树是路径长度最短的二叉树

• 权(weight):将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权

• 1结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积

• 树的带权路径长度：树中所有叶子节点的带权路径长度之和。

 哈夫曼树：最优树 带权路径长度最短的树

满二叉树不一定是最优二叉树

• 哈夫曼树中权越大的叶子离根越近

• 具有相同带权结点的哈夫曼树不唯一

2、哈夫曼树的构造算法

2.1  哈夫曼算法

1. 构造森林全是根

2. 选用两小造新树

3. 删除两小添新人

4. 重复 2、3 剩单根

包含n棵树的森林要经过n-1次合并才能形成哈夫曼树，共产生n-1个新结点

包含n个叶子节点的哈夫曼树中共有2n-1个结点

总结：

1. 在哈夫曼算法中，初始时有n棵二叉树，要经过n-1次合并最终形成哈夫曼树。

2. 经过n-1此=次合并产生n-1个新结点，且这 n-1 个新结点都是具有两个孩子的分支结点

3. 哈夫曼树中共有n+n-1 = 2n-1 个结点，且所有的分支结点的度都不为 1。

2.2 哈夫曼树构造算法实现

采用顺序存储结构— 一维结构数组

// 结点类型定义
typedef struct{
	int weight;
	int parent,lch,rch;
}HTNode,*HuffmanTree;

// 找出森林中权值最小的两个
void Select(HuffmanTree HT,int n,int &s1,int &s2) {
	int minum;
	int i;
	for(i=1;i<=n;i++){
		if(HT[i].parent == 0){
			minum = i;
			break;
		}
	}
	for(i = 1;i<=n;i++){
		if(HT[i].parent == 0){
			if(HT[i].weight<HT[minum].weight){
				minum = i;
			}
		}
	}
	s1 = minum;
	for(i=1;i<=n;i++){
		if(HT[i].parent == 0&& i!=s1){
			minum = i;
			break;
		}
	}
	for(i = 1;i<=n;i++){
		if(HT[i].parent == 0&& i!=s1){
			if(HT[minum].weight<HT[minum].weight){
				minum = i;
			}
		}
	}
	s2 = minum;
}

// 建立哈夫曼树 
void CreatHuffmanTree(HuffmanTree HT,int n){
	int m,i,s1,s2;
	if(n<=1){
		return ;
	}
	m = 2*n-1;			// 数组共2n-1个元素
	HT = new HTNode[m+1];	// 0号单元未用，HT[m]表示根节点 
	for(i=1;i<=m;i++){		// 将2n-1个元素的lch,rch,parent设置为0 
		HT[i].lch = 0;
		HT[i].rch = 0;
		HT[i].parent = 0;
	} 
	for(i = 1;i<=n;i++){	// 输入前n个元素的weight值 
		scanf("%d",HT[i].weight);
	}
	// 初始化结束，下面开始建立哈夫曼树 
	for(i=n+1;i<=m;i++){
		Select(HT,i-1,s1,s2);
		HT[s1].parent = i;
		HT[s2].parent = i;
		HT[i].lch = s1;
		HT[i].rch = s2;
		HT[i].weight = HT[s1].weight+HT[s2].weight;
	} 
} 

3、哈夫曼编码

3.1 哈夫曼编码

1. 统计字符集中每个字符在电文中出现的平均概率（概率越大，要求编码越短）

2. 利用哈夫曼树的特点：权越大的叶子离根越近，将每个字符的概率值作为权重，构建哈夫曼树。则概率越大的结点，路径越短

3. 在哈夫曼树的每个分支上标上0或1：

   • 结点的左分支标0，右分支标1

   • 把从根到每个叶子的路径上的标号连接起来，作为该叶子代表的字符的编码。

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

//存放哈夫曼编码
typedef char** HuffmanCode;

// 结点类型定义
typedef struct{
	int weight;
	int parent,lch,rch;
}HTNode,*HuffmanTree; 

// 哈夫曼编码 
void  CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n){
	HC = new char*[n+1];
	char *cd = new char[n];
	cd[n-1] = '\0';
	int start,c,f,i;
	for(i=1;i<=n;i++){
		start = n-1;
		c = i;
		f = HT[i].parent;
		while(f!=0){
			start--;
			if(HT[f].lch == c){
				cd[start] = '0';
			}else{
				cd[start] = '1';
			}
			c = f;
			f = HT[f].parent;
		}
		HC[i] = new char[n-start];
		strcpy(HC[i],&cd[start]);
	}
	delete cd;		// 释放临时空间 
}

3.2 文件的编码和解码