C++实现哈夫曼树简单创建与遍历的方法
本文以实例形式讲述了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，知道森林中只有一棵树位置，这棵树就是哈夫曼树.
#include<iostream>
usingnamespacestd;
#defineLEAFNUM10//叶子节点数，也就是权值树
#defineHUFNUM2*LEAFNUM
#defineMAXWEIGHT999.9
//*********存储结构***********
classHufTree;
//*****Node**********
classNODE
{
private:
charData;//节点的数据域
doubleWeight;//节点的权值域
intLchild,Rchild,Parent;//节点的左孩子右孩子及双亲域
public:
NODE()//构造函数
{
Data='\0';
Weight=0;
Lchild=-1;
Rchild=-1;
Parent=-1;//给节点的数据初始化
}
intRe_L(){returnLchild;}
intRe_R(){returnRchild;}
charRe_Data(){returnData;}
doubleRe_Weight(){returnWeight;}
friendclassHufTree;//声明友元
};//Node
//********HufTree类**********
classHufTree
{
private:
intNodeNum;
NODEHufArry[HUFNUM];
public:
HufTree(){NodeNum=0;}
voidSetHuf(int,double,char);//设置权值与数据域
voidCreatHuf();//创建哈夫曼树
voidSelectMin(int,int&,int&);//查找哈夫曼树种两个权值最小的树
voidFind_Root_and_Print();//查找树根节点位置
voidPrintHuf(int);//遍历哈夫曼树
};//huftree
voidHufTree::SetHuf(inti,doublewei,charch)
{
HufArry[i].Data=ch;
HufArry[i].Weight=wei;
}
voidHufTree::CreatHuf()
{
cout<<"每次查询两个最小树的位置:"<<endl;
for(inti=LEAFNUM;i<HUFNUM-1;i++)
{
intp1=0;
intp2=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;
}
voidHufTree::SelectMin(inti,int&p1,int&p2)
{
intleast1=MAXWEIGHT;
intleast2=MAXWEIGHT;
for(intj=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;
}
}
}
}
}
voidHufTree::Find_Root_and_Print()
{
introot;
for(inti=0;i<HUFNUM-1;i++)
{
if(HufArry[i].Parent==-1)
{
root=i;
break;
}
}
PrintHuf(root);
}
voidHufTree::PrintHuf(intposition)
{
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);
}
}
}
intmain()
{
HufTreeTree;
cout<<"请输入"<<LEAFNUM<<"对(权值,数据):"<<endl;
doublewei;
charch;
for(inti=0;i<LEAFNUM;i++)
{
cin>>wei;
cin>>ch;
Tree.SetHuf(i,wei,ch);
}
Tree.CreatHuf();//创建哈夫曼树
Tree.Find_Root_and_Print();//遍历哈夫曼树
return0;
}
测试结果：
1a 2b 5c 7d 4e 13f 3g 6h 11i 8l