哈夫曼树的建立与操作

实验六哈夫曼树的建立与操作

一、实验要求和实验内容

1、输入哈夫曼树叶子结点（信息和权值）

2、由叶子结点生成哈夫曼树内部结点

3、生成叶子结点的哈夫曼编码

4、显示哈夫曼树结点顺序表

二、详细代码（内包含了详细的注释）：

#include

using namespace std;

typedef char Elemtype;

struct element

{

int weight;

Elemtype date;

element* lchild,*rchild;

};

class HuffmanTree

{

public:

HuffmanTree()//构造函数

{

cout<<"请输入二叉树的个数"<

cin>>count;

element *s=new element[count];//s为指向数组的指针，保存指向数组的地址

for(int i=0;i

{

cout<<"输入第"<

cin>>s[i].weight;

cout<<"输入第"<

cin>>s[i].date;

s[i].lchild=NULL;

s[i].rchild=NULL;

}//以上为初始化每一个结点

element * *m=new element*[count];//m为指向数组成员的地址的指针，保存【指向数组成员地址的指针】的地址

for(int i=0;i

{

m[i]=s+i;//把数组成员i地址赋给m[i]（m[i]大致意思等效于*m）}

//以下为哈夫曼的构造过程

element*q;

for(int i=0;i

{

int a=32767,b=32767;//a,b为两个存当前最小值的两个临时变量，初始化为32767（int型能达到的最大的值）

for(int i=1;i

{

if(m[i]!=NULL)

if(m[i]->weight

{

a=m[i]->weight;

return1=i;

}

}

for(int i=0;i

{

if(m[i]!=NULL)

if(m[i]->weightweight>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<<"哈夫曼树构造成功"<

}

void HufumanCoding(element* bt,int len=0)//求哈夫曼编码,len为哈夫曼编码的位数默认为0

{

if(bt)//当bt不为空时进入

{

if(!bt->lchild&&!bt->rchild)//当此结点为叶子结点时进入

{

cout<<"权值为"<date<<"结点的哈夫曼编码为：";

for(int i=0;i

cout<

cout<

}

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);

}

三、运行结果