数据结构——详解哈夫曼树及哈夫曼编码与其具体代码实现_哈夫曼二叉树举例

哈夫曼树

首先我们需要明白什么是哈夫曼树：

概念上说，哈夫曼树是给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树。

叶子结点的权值：对叶子结点赋予的一个有意义的数值量。

二叉树的带权路径长度：设二叉树具有n个带权值的叶子结点，从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和。 记为：

看起来好像有点抽象，那么我来解释一下：

比如我们给定4个叶子结点，其权值分别为{2，3，4，7}，那么，可以构造出形状不同的多个二叉树。

比如下面这三个二叉树，其叶子结点的权值均为2，3，4，7，那么哪个才是二叉树呢？

我们根据其二叉树的带权路径长度来判断

比如第一个，其长度为：

（2+3+4+7）×2=32

第二个的长度为：

（4+7）×3+3×2+2×1=41

第三个的长度为：

（2+3）×3+4×2+7×1=30

通过比较可以发现，第三个二叉树便是我们所要求的哈夫曼树。

我们同时可以发现，凡是哈夫曼树，均有以下的特点：

哈夫曼树的特点：

1. 权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。

2. 只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点。

显然，如果每次判断哈夫曼树都要把所有二叉树列出来然后比较是不可取的，我们有哈夫曼算法可以直接求出哈夫曼树：

哈夫曼算法

哈夫曼算法基本思想：

⑴ 初始化：

由给定的n个权值{w1，w2，…，wn}构造n棵只有一个根结点的二叉树，从而得到一个二叉树集合F＝{T1，T2，…，Tn}；

⑵ 选取与合并：

在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和；

⑶ 删除与加入：

在F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到F中；

⑷ 重复⑵、⑶两步，当集合F中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。

可能有的读者暂时还没有理解，我们用一个实例来说明哈夫曼算法：

求叶子结点W＝{2，4，5 ，3} 哈夫曼树的构造过程：

第1步：初始化：

我们选择权值最小的两个叶子结点，将其相加作为新的叶子结点

第2步：选取与合并

第三步 加入与删除

重复第二步：

在这可能读者会有疑问，为什么不选第三个5呢？答案是当然可以选，这也说明了我们构造的哈夫曼树可能并不唯一，但效果是一样的

重复第三步:

重复第二步

重复第三步

到这一颗哈夫曼树就被我们构造出来了，是不是很简单呢？这就是哈夫曼算法

哈夫曼编码

现在哈夫曼算法的原理我们清楚了，那么怎样用代码来实现呢？

1.首先，我们应该先定义一个哈夫曼算法的存储结构。设置一个数组huffTree[2n-1]保存哈夫曼树中各点的信息，数组元素的结点结构 。

至于为什么是2n-1，在后面我会讲到

其中：weight：权值域，保存该结点的权值；
lchild：指针域，结点的左孩子结点在数组中的下标；
rchild：指针域，结点的右孩子结点在数组中的下标；
parent：指针域，该结点的双亲结点在数组中的下标。

2.1. 数组huffTree初始化，所有元素结点的双亲、左右孩子都置为-1；

2.2.数组huffTree的前n个元素的权值置给定值w[n]；

2.3.进行n-1次合并

2.3.1 在二叉树集合中选取两个权值最小的根结点，其下标分别为i1, i2；

2.3.2 将二叉树i1、i2合并为一棵新的二叉树k；

我们同样以叶子结点为2、3、4、5举例：

1.n=4，先初始化为如下图所示

2.将2和3合并，同时将权值为2和3的双亲改为4，将新加入的权值为5的结点左右孩子改为0和3

3.重复上述过程即可

我们可以发现，当叶子结点个数为4时，最终得到的哈夫曼数组恰好为2×4-1=7，因此在构造时需要2n-1个空间来存储

哈夫曼数的应用在此不再赘述

哈夫曼数的初始化：

void HuffmanTree(element huffTree[ ], int w[ ], int n ) {
    for (i = 0; i <2*n-1; i++) {
        huffTree [i].parent = -1;
        huffTree [i].lchild = -1;
        huffTree [i].rchild = -1;   
    }//全部置为-1
    for (i = 0; i < n; i++) 
        huffTree[i].weight = w[i];//前n个元素的权重赋值进去
    for (k = n; k < 2*n-1; k++) {
        Select(huffTree, i1, i2); 
        huffTree[k].weight = huffTree[i1].weight+huffTree[i2].weight;
        huffTree[i1].parent = k; huffTree[i2].parent = k; 
        huffTree[k].lchild = i1; huffTree[k].rchild = i2;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

下面给出一个哈夫曼树应用的实例代码，可以根据英文字母出现的频率给出其最佳编址方案：（代码解释写的很详细，大家可以认真阅读）

#include<iostream>
#include<fstream>//文件输入流的头文件
#include<conio.h>//getch()函数头文件
#include<string>//新版vc的getch()函数头文件
using namespace std;

char OutputCode[1000];//待输出的哈夫曼编码
string HuffCode[26];//哈夫曼编码
char sentence[100];
struct element
{
	char data;//数据
	double weight;//权重
	bool root_flag;//判断是否被标记为根结点
	int lchild,rchild,parent;
};
void HuffmanTree(element huffTree[],int n);
void Select(element huffTree[],int n,int &i1,int &i2);
void DFS_PreOrder(element huffTree[],int i,int k);
void translate(string HuffCode[],char sentence[]);
int main()
{
	fstream fcin;
	fcin.open("HuffTree.txt",ios::in);
	int N=0;
	element huffTree[100];
	while(!fcin.eof())
	{
		fcin>>huffTree[N].data>>huffTree[N].weight;//写入哈夫曼树的结点数据值，和数据所对应的权重
		N++;
	}
	HuffmanTree(huffTree,N);//构造哈夫曼树
	DFS_PreOrder(huffTree,2*N-2,0);//前序深度优先遍历哈夫曼树
	system("CLS");			
	fcin.close();

	//功能模块
	char X;
	int i=0;
	system("color A0");
	while(true)
	{
		cout<<"请输入需要的功能N："<<endl;
		cout<<"0.退出\n";
		cout<<"1.输出各个字母所对应的哈夫曼编码\n";
		cout<<"2.将句子翻译成哈夫曼编码\n";
		cin>>X;
		if(X=='0')break;//输入'0'退出
		switch(X)
		{
		case '1':
			DFS_PreOrder(huffTree,2*N-2,0);//前序深度优先遍历哈夫曼树				
			cout<<"--请按任意键继续--\n";
			_getch();
			system("CLS");
			break;
		case '2':
			sentence[0]='\0';
			cout<<"请输入要翻译的英文序列:";
			cin>>sentence;
			translate(HuffCode,sentence);//翻译成哈夫曼编码
			cout<<"--请按任意键继续--\n";
			_getch();
			system("CLS");
			break;
		default:
			cout<<"输入错误，请重新输入!\n";
			cout<<"--请按任意键继续--\n";
			_getch();
			system("CLS");
		}
	}
	return 0;
}
void HuffmanTree(element huffTree[],int n)
{
	int i;
	for(i=0;i<2*n-1;i++)
	{
		huffTree[i].parent=-1;
		huffTree[i].lchild=-1;
		huffTree[i].rchild=-1;
		huffTree[i].root_flag=0;//初始化时，令root_flag=0，即所有的结点都不是根结点
	}
	for(i=0;i<n;i++)
		huffTree[i].root_flag=1;//然后，令叶子结点的根结点属性全为1，即叶子结点都设置为根结点
	int i1=-1,i2=-1;//将权重最小的两个点初始化为-1
	for(int k=n;k<2*n-1;k++)
	{
		huffTree[k].data='#';//让哈夫曼树上非叶子结点的数据为'#'，即空数据
		Select(huffTree,n,i1,i2);//寻找两个权重最小的根结点
		huffTree[i1].parent=k;		huffTree[i2].parent=k;//两个根结点的parent设置为k
		huffTree[k].lchild=i1;		huffTree[k].rchild=i2;//k结点的左右孩子设置为i1,i2
		huffTree[k].weight=huffTree[i1].weight+huffTree[i2].weight;//k结点的权重等于i1，i2的权重相加
		huffTree[k].root_flag=1;//把k结点标记为根结点
		huffTree[i1].root_flag=0;	huffTree[i2].root_flag=0;//把i1，i2结点标记为非根结点
	}
}
void Select(element huffTree[],int n,int &i1,int &i2)//寻找两个权重最小的根结点函数，这里的i1，i2设置为 &变量名，即函数会对这两个变量的值进行修改
{
	int i;
	double weight=1000;//初始化权重为一个大数
	for(i=0;i<2*n-1;i++)//先遍历一遍求i1
		if(huffTree[i].root_flag&&huffTree[i].weight<weight)//如果是根节点 则找出最小的为i1
		{
			weight=huffTree[i].weight;
			i1=i;
		}
	weight=1000;//再次设置权重为一个大数求i2
	for(i=0;i<2*n-1;i++)//再遍历一遍求i2
		if(huffTree[i].root_flag&&huffTree[i].weight<weight&&i!=i1)//如果是根节点并且不是i1，则找出最小的为i2
		{
			weight=huffTree[i].weight;
			i2=i;
		}
}

void DFS_PreOrder(element huffTree[],int i,int k)//前序深度优先遍历哈夫曼树，这里的i参数是根结点的数组下标，k结点是哈夫曼编码的数组下标
{
	if(huffTree[i].lchild!=-1)//如果有左孩子，则遍历左子树
	{
		OutputCode[k]='0';//遍历一次左子树，把哈夫曼编码置0
		DFS_PreOrder(huffTree,huffTree[i].lchild,k+1);
	}
	if(huffTree[i].rchild!=-1)//如果有右孩子，则遍历右子树
	{
		OutputCode[k]='1';//遍历一次右子树，把哈夫曼编码置1
		DFS_PreOrder(huffTree,huffTree[i].rchild,k+1);
	}
	if(huffTree[i].data!='#')//如果左子树右子树都不存在，则是叶子结点，这时候需要输出结点
	{
		OutputCode[k]='\0';//给哈夫曼编码结束符
		cout<<huffTree[i].data<<"的编码为:";
		for(int t=0;OutputCode[t]!='\0';t++)
			cout<<OutputCode[t];//输出哈夫曼编码
		cout<<endl;
		HuffCode[huffTree[i].data-'A']=OutputCode;//保存下来该字母的哈夫曼编码
	}
}

void translate(string HuffCode[],char sentence[])//翻译函数
{
	int i=0;
	cout<<"翻译后的哈夫曼编码为:";
	while(sentence[i]!='\0')
	{
		if(sentence[i]>='a'&&sentence[i]<='z')
			cout<<HuffCode[sentence[i]-'a'];
		else if(sentence[i]>='A'&&sentence[i]<='Z')
			cout<<HuffCode[sentence[i]-'A'];
		i++;
	}
	cout<<endl;
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154

需要读的文件内容为：（将其存储在txt文件中，命名为HuffTree）

E	12.25
T	9.41
A	8.19
O	7.26
I	7.10
N	7.06
R	6.85
S	6.36
H	4.57
D	3.91
C	3.83
L	3.77
M	3.34
P	2.89
U	2.58
F	2.26
G	1.71
W	1.59
Y	1.58
B	1.47
K	0.41
J	0.14
V	1.09
X	0.21
Q	0.09 
Z	0.08
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

运行结果如下：