实验六哈夫曼树的建立与操作
一、实验要求和实验内容
1、输入哈夫曼树叶子结点（信息和权值）
2、由叶子结点生成哈夫曼树内部结点
3、生成叶子结点的哈夫曼编码
4、显示哈夫曼树结点顺序表
二、详细代码（内包含了详细的注释）：
#include<iostream>
using namespace std;
typedef char Elemtype;
struct element
{
int weight;
Elemtype date;
element* lchild,*rchild;
};
class HuffmanTree
{
public:
HuffmanTree()//构造函数
{
cout<<"请输入二叉树的个数"<<endl;
cin>>count;
element *s=new element[count];//s为指向数组的指针，保存指向数组的地址
for(int i=0;i<count;i++)
{
cout<<"输入第"<<i+1<<"个节点的权值"<<endl;
cin>>s[i].weight;
cout<<"输入第"<<i+1<<"个节点的内容"<<endl;
cin>>s[i].date;
s[i].lchild=NULL;
s[i].rchild=NULL;
}//以上为初始化每一个结点
element * *m=new element*[count];//m为指向数组成员的地址的指针，保存【指向数组成员地址的指针】的地址
for(int i=0;i<count;i++)
{
m[i]=s+i;//把数组成员i地址赋给m[i]（m[i]大致意思等效于*m）}
//以下为哈夫曼的构造过程
element*q;
for(int i=0;i<count-1;i++)
{
int a=32767,b=32767;//a,b为两个存当前最小值的两个临时变量，初始化为32767（int型能达到的最大的值）
for(int i=1;i<count;i++)
{
if(m[i]!=NULL)
if(m[i]->weight<a)
{
a=m[i]->weight;
return1=i;
}
}
for(int i=0;i<count;i++)
{
if(m[i]!=NULL)
if(m[i]->weight<b&&m[i]->weight>a)
{
b=m[i]->weight;
return2=i;
}
}
q=new element;//构建一棵新树
q->weight=m[return1]->weight+m[return2]->weight;
q->lchild=m[return1];
q->rchild=m[return2];
m[return1]=q;
m[return2]=NULL; //用新树替换原来的两子树,并置空一个数
}
boot=q;//把最后取得的哈夫曼树的头结点即q赋值给boot
cout<<"哈夫曼树构造成功"<<endl;
}
void HufumanCoding(element* bt,int len=0)//求哈夫曼编码,len为哈夫曼编码的位数默认为0
{
if(bt)//当bt不为空时进入
{
if(!bt->lchild&&!bt->rchild)//当此结点为叶子结点时进入
{
cout<<"权值为"<<bt->date<<"结点的哈夫曼编码为：";
for(int i=0;i<len;i++)
cout<<m[i];
cout<<endl;
}
else
{
m[len]=0; HufumanCoding(bt->lchild,len+1);
m[len]=1; HufumanCoding(bt->rchild,len+1);
}
}
}
element* ReturnBoot()
{
return boot;
}
private:
int count;//结点数
int return1,return2;//权值最小的节点的在数组中的位置
element* boot;
int m[20];//存储哈夫曼编码
};
int main()
{
element* m;
HuffmanTree a;
m=a.ReturnBoot();
a.HufumanCoding(m);
}
三、运行结果。