哈夫曼树实验报告

数据结构实验报告

（一）实验目的和要求：

实现哈夫曼树

（二）实验主要内容：

输入5个带权值的结点，建立哈夫曼树，并输出。

（三）主要仪器设备

PC机，Windows 10，Dev C++

（四）实验原理

利用哈夫曼算法可以构造出相应的哈夫曼树。

（五）实验步骤与调试分析

输入结点权值1，2，3，4，5，构造对应哈夫曼树，然后输出每个结点的权值，左孩子，右孩子以及双亲。

（六）实验结果与分析

（七）附录（源程序）

#include

using namespace std;

struct element{

int weight;

int lchild,rchild,parent;

};

void HuffmanTree(element huffTree[],int w[],int n){

int i;

int i1,i2;

for(i=0;i

huffTree[i].parent=-1;

huffTree[i].lchild=-1;

huffTree[i].rchild=-1;

huffTree[i].weight=0;

}

for(i=0;i

huffTree[i].weight=w[i];

for(int k=n;k

i1=0,i2=1;

if(huffTree[0].weight>huffTree[1].weight)i2=0,i1=1; for(i=2;i

if(huffTree[i].weight

huffTree[i1].parent=k;

huffTree[i2].parent=k;

huffTree[k].weight=huffTree[i1].weight+huffTree[i2].weight; w[k]=huffTree[k].weight;

huffTree[k].lchild=i1;

huffTree[k].rchild=i2;

w[i1]=huffTree[i1].weight;w[i2]=huffTree[i2].weight; huffTree[i1].weight=1000;huffTree[i2].weight=1000; }

for(i=0;i

huffTree[i].weight=w[i];

huffTree[2*n-1].parent=-1;

}

int main(){

int w[9]={1,2,3,4,5};

element huffTree[9];

int n=5;

HuffmanTree(huffTree,w,n);

for(int i=0;i

cout

getchar();

return 0;

} lchild: