本文以实例形式讲述了C++实现哈夫曼树简单创建与遍历的方法，比较经典的C++算法。
本例实现的功能为：给定n个带权的节点，如何构造一棵n个带有给定权值的叶节点的二叉树，使其带全路径长度WPL最小。
据此构造出最优树算法如下：
哈夫曼算法：
1. 将n个权值分别为w1,w2,w3,....wn-1，wn的节点按权值递增排序,将每个权值作为一棵二叉树。构成n棵二叉树森林F={T1,T2,T3,T4,...Tn}，其中每个二叉树都只有一个权值，其左右字数为空
2. 在森林F中选取根节点权值最小二叉树，作为左右字数构成一棵新的二叉树，并使得新的二叉树的根节点为
其左右字数权值之和,其中叶子都是最初的树
3. 在森林F中删除这两棵树，同时将新得到的二叉树代替这两个树加入到森林F中，因此森林中二叉树的个数比以前少一颗
4. 对新的森林重复2和3，知道森林中只有一棵树位置，这棵树就是哈夫曼树.
|
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
|
#include <iostream>
using namespace std;
#define LEAFNUM 10 //叶子节点数，也就是权值树
#define HUFNUM 2*LEAFNUM
#define MAXWEIGHT 999.9
//*********存储结构***********
class HufTree;
//***** Node**********
class NODE
{
private:
char Data; //节点的数据域
double Weight; //节点的权值域
int Lchild,Rchild,Parent; //节点的左孩子右孩子及双亲域
public:
NODE() //构造函数
{
Data = '\0';
Weight = 0;
Lchild = -1;
Rchild = -1;
Parent = -1; //给节点的数据初始化
}
int Re_L(){return Lchild;}
int Re_R(){return Rchild;}
char Re_Data(){return Data;}
double Re_Weight(){return Weight;}
friend class HufTree; //声明友元
};//Node
//********HufTree类**********
class HufTree
{
private:
int NodeNum;
NODE HufArry[HUFNUM];
public:
HufTree(){NodeNum = 0;}
void SetHuf(int,double,char); //设置权值与数据域
void CreatHuf(); //创建哈夫曼树
void SelectMin(int,int&,int&); //查找哈夫曼树种两个权值最小的树
void Find_Root_and_Print(); //查找树根节点位置
void PrintHuf(int); //遍历哈夫曼树
};//huftree
void HufTree::SetHuf(int i,double wei,char ch)
{
HufArry[i].Data = ch;
HufArry[i].Weight = wei;
}
void HufTree::CreatHuf()
{
cout<<"每次查询两个最小树的位置:"<<endl;
for(int i = LEAFNUM; i < HUFNUM - 1; i++)
{
int p1 = 0;
int p2 = 0;
SelectMin(i,p1,p2); //找出当前树种权值最小的两颗树
cout<<p1<<" < - > "<<p2<<endl;
HufArry[p1].Parent = i; //设置两颗最小树的双亲
HufArry[p2].Parent = i;
HufArry[i].Lchild = p1; //设置这棵3节点的树的根的权值以及孩子
HufArry[i].Rchild = p2;
HufArry[i].Weight = HufArry[p1].Weight + HufArry[p2].Weight;
}
cout<<"************************"<<endl;
}
void HufTree::SelectMin(int i,int &p1,int &p2)
{
int least1 = MAXWEIGHT;
int least2 = MAXWEIGHT;
for(int j = 0; j < i; j++)
{
if(HufArry[j].Parent == -1)
{
if(HufArry[j].Weight < least1)
{
least2 = least1;
least1 = HufArry[j].Weight;
p2 = p1;
p1 = j;
}
else
{
if(HufArry[j].Weight < least2)
{
least2 = HufArry[j].Weight;
p2 = j;
}
}
}
}
}
void HufTree::Find_Root_and_Print()
{
int root;
for(int i = 0; i < HUFNUM - 1; i++)
{
if(HufArry[i].Parent == -1)
{
root = i;
break;
}
}
PrintHuf(root);
}
void HufTree::PrintHuf(int position)
{
if(NodeNum == LEAFNUM)
{
return;
}
else
{
if(HufArry[position].Data != '\0') //如果是叶子节点
{
cout<<"权值:"<<HufArry[position].Weight<<"<-> 数据:"<<HufArry[position].Data<<" 此节点为叶子"<<endl;
NodeNum = NodeNum + 1;
}
else
{
cout<<"权值:"<<HufArry[position].Weight<<" 此节点无数据域,不是叶子"<<endl;
PrintHuf(HufArry[position].Lchild);
PrintHuf(HufArry[position].Rchild);
}
}
}
int main()
{
HufTree Tree;
cout<<"请输入"<<LEAFNUM<<"对(权值,数据):"<<endl;
double wei;
char ch;
for(int i = 0; i < LEAFNUM; i++)
{
cin>>wei;
cin>>ch;
Tree.SetHuf(i,wei,ch);
}
Tree.CreatHuf(); //创建哈夫曼树
Tree.Find_Root_and_Print(); //遍历哈夫曼树
return 0;
}
|
测试结果：
|
1
2
3
4
5
6
7
8
9
10
|
1 a
2 b
5 c
7 d
4 e
13 f
3 g
6 h
11 i
8 l
|