数据结构——哈夫曼树及其应用

哈夫曼的基本概念

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

 

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

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

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

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

树的带权路径长度(WPL)：树中所有叶子结点的带权路径长度之和
记作：$$WPL=\sum _{i=0}^k{w}_k{l}_k$$
$\omega$——权值  $l_k$——结点到根的路径长度

 
 

哈夫曼树：最优树——带权路径长度(WPL)最短的树

1. 满二叉树不一定是哈夫曼树
2. 哈夫曼树中权越大的叶子离根越近
3. 具有相同带权结点的哈夫曼树不唯一

 
 

哈夫曼树的构造算法

 

贪心算法：构造哈夫曼树首先选择权值小的叶子结点

哈夫曼算法（构造哈夫曼树的方法）

口诀：

1. 构造森林全是根；
2. 选用两小造新树；
3. 删除两小添新人
4. 重复2、3剩单根

 

哈夫曼树的结点的度数为0或2，没有度为1的结点；

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

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

总结：

1. 在哈夫曼算法中，初始时有n棵二叉树，要经过n-1次合并最终形成哈夫曼树
2. 经过n-1次合并产生n-1个新结点，且这n-1个新结点都是具有两个孩子的分支结点

可见：哈夫曼树中共有 n+n-1 = 2n-1个结点，且其所有的分支结点的度均不为1
 
 

哈夫曼树构造算法的实现

 
采用顺序存储结构—— 一维结构数组
结点类型定义：

typedef struct{
	int weight;
	int parent, lch, rch;
}HTNode, *HuffmanTree;
1
2
3
4

哈夫曼树中共有2n-1个结点，不使用0下标，数组大小为2n
 

例如：第一个结点权值为5，即可表示为 H[i].weight = 5;

 

例：有n = 8，权值为 W = {7, 19, 2, 6, 32, 3, 21, 10}, 构造哈夫曼树

1. 初始化HT [1…2n-1]：lch = rch = parent = 0；
2. 输入初始n个叶子结点：置HT[1…n]的weight值
3. 进行以下n-1次合并，一次产生n-1个结点HT[i], i = n+1…2n-1
   a) 在HT[1…i-1中选两个未被选过（从 parent==0 的结点中选）的weight最小的两个结点HT[s1]和HT[s2]，s1、s2为两个最小结点下标；
   b) 修改HT[s1]和HT[s2]的parent值： HT[s1].parent=i;  HT[s2].parent = i;
   c) 修改新产生的HT[i]：
     1) HT[i].weight = HT[s1].weigth + HT[s2].weight;
     2) HT[i].lch = s1; HT[i].rch = s2;

//构造哈夫曼树——哈夫曼算法
void CreatHuffmanTree(HuffmanTree &HT, int n){
	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)
		cin >> HT[i].ewight;	//输入前n个元素的weight值
	//初始化结束，下面开始建立哈夫曼树

	//合并产生n-1个结点——构造哈夫曼树
	for(i = n + 1; i <= m; i++){	
		Select(HT, i - 1, s1, s2);	//在HT[k] (1 ≤ k ≤ i-1)中选择两个其双亲域为0，
									//且权值最小的结点，并返回他们在HT中的序号s1和s2
									
		HT[s1].parent = i;		//表示从F中删除s1，s2
		HT[s2].parent = i;
		
		HT[i].lch = s1;			//s1，s2分别为i的左右孩子
		HT[i].rch = s2;

		HT[i].weight = HT[s1].weight +HT[s2].weight;	//i的权值为左右孩子权值之和
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

 

例：设n = 8， w = {5, 29, 7, 8, 14, 23, 3, 11}，试设计Huffman code

(m = 2*8-1 = 15)


 
 

哈夫曼编码

问题：什么样的前缀码能使得电文总长最短 ？ —— 哈夫曼编码

1. 统计字符集中每个字符在电文中出现的平均概率（概率越大，要求编码越短）
2. 利用哈夫曼树的特点：权越大的叶子离根越近；将每个字符的概率值作为权值，构造哈夫曼树，则概率越大的结点，路径越短
3. 在哈夫曼树的每个分支上标上0或1：
     结点左分支标0，右分支标1
     把从根到每个叶子的路径上的标号连接起来，作为该叶子代表的字符的编码

 

哈夫曼编码算法的讲解：https://www.bilibili.com/video/BV1nJ411V7bdp=106&spm_id_from=pageDriver

哈夫曼编码算法的实现：

//从叶子到逆根向求每个字符的哈夫曼编码，存储在编码表HC中
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n){
	HC = new char *[n + 1];			//分配n个字符编码的头指针矢量
	cd = new char [n];				//分配临时存放编码的动态数组空间
	cd[n - 1] = '\0' ;				//编码结束符
	for(i = 1; i <= n; ++i){		//逐个字符求哈夫曼编码
		start = n - 1;
		c = i;
		f = HT[i].parent;
		while(f != 0){			//从叶子结点开始向上回溯，直到根结点
			--start;			//回溯一次start向前指一个位置
			if(HT[f].lchild == c)		//结点c是f的左孩子，则生产代码0
				cd[start] = '0' ;		
			else						//结点c是f的右孩子，则生成代码1
				cd[start] = '1' ;
			c = f;				//继续向上回溯
			f = HT[f].parent;
		}						//求出第i个字符的编码	
		HC[i] = new char [n - start];		//为第i个字符串编码分配空间
		strcpy(HC[i], &cd[start]);			//将求得的编码从临时空间cd复制到HC的当前行中
	}
	delete cd;		//释放临时空间
} //CreatHuffanCode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

 
 

文件的编码和解码

一、编码：

 ① 输入各字符及其权值

 ② 构造哈夫曼树——HT[i]

 ③ 进行哈夫曼编码——HC[i]

 ④ 查HC[i]，得到各字符的哈夫曼编码

二、解码：

 ① 构造哈夫曼树

 ② 依次读入二进制码

 ③ 读入0，则走向左孩子；读入1，则走向右孩子

 ④ 一旦到达某叶子时，即可译出字符

 ⑤ 然后再从根出发继续译码，直到结束

讲解：https://www.bilibili.com/video/BV1nJ411V7bd?p=107