树的应用-哈夫曼编码

～ 第学期 专业

班级： 学号： 姓名：

实验三 树的应用

一、 实验题目：

树的应用——哈夫曼编码

二、 实验内容：

1. 编写程序，完成以下功能：

（1） 建立二叉树B ；

（2） 输出二叉树B ；

（3） 输出二叉树B 的深度；

（4） 输出二叉树B 的宽度；

（5） 输出二叉树B 的节点个数；

（6） 输出二叉树B 的叶子节点个数

2. 编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。

从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，求出各字符的哈夫曼编码。要求：

（1） 输出存放哈夫曼树的数组HT 的初态和终态；

（2） 输出每个字符的哈夫曼编码；

（3） 输入由上述若干字符组成的字符串，对电文进行编码并输出；

（4） （选作）输入电文的哈夫曼编码，进行译码并输出。

三、程序设计过程及源代码：

(一) 设计思路：首先初始化一个二叉树链，其中建立一个栈用来建立之前根节点和其他孩子节点的关系。主要思路就是将根节点与其左右节点进栈，然后依次退栈，知道最后栈为空，二叉树构建完成。求高度、宽度和二叉树输出，以及求节点数、叶子节点数的时候都用到了递归算法，特别强调的是不仅要逐层递加（扫描每一层），还要扫描每一层上的节点数，用数组n[i]表示每一层节点。

源代码：

#include

#include

#define MaxSize 30

typedef struct node

{

int data;

struct node *lchild;

struct node *rchild;

}BTnode;

void CreateBTnode(BTnode *&b,char *str)

{ BTnode *st[MaxSize],*p;

int top=-1,k,j=0;

char ch;

b=NULL;

ch=str[j];

while(ch!='\0')

{ switch(ch)

{

case'(':top++;st[top]=p;k=1;break;

case')':top--;break;

case',':k=2;break;

default:p=(BTnode*)malloc(sizeof(BTnode));

p->data=ch;p->lchild=p->rchild=NULL;

if(b==NULL)

b=p;

else

{ switch(k)

{ case 1:st[top]->lchild=p;break;

case 2:st[top]->rchild=p;break; }

}

}

j++;

ch=str[j];

}

}

void DispBTnode(BTnode *b)

{

if(b!=NULL)

{

printf("%c",b->data);

if(b->lchild!=NULL||b->rchild!=NULL)

{

printf("(");

DispBTnode(b->lchild);

if(b->rchild!=NULL) printf(",");

DispBTnode(b->rchild);

printf(")");

}

}

}

int BTnodeHeight(BTnode *b)//高度

{

int lchildh,rchildh,h;

if(b==NULL) return 0;

else

{

lchildh=BTnodeHeight(b->lchild);

rchildh=BTnodeHeight(b->rchild);

h=(lchildh>rchildh)?(lchildh+1):(rchildh+1);

return h;

}

}

int LeafNodes(BTnode *b)//叶子结点的个数

{ int num1,num2,n;

if(b==NULL) n=0;

else

{

if(b->lchild==NULL && b->rchild==NULL)

n=1;

else

{

num1=LeafNodes(b->lchild);

num2=LeafNodes(b->rchild);

n=num1+num2;

}

}

return n;

}

int Nodes(BTnode *b)//结点个数

{

int n;

if (b==NULL) n=0;

else

n=Nodes(b->lchild)+Nodes(b->rchild)+1;

return n;

}

void BTWidth(BTnode *b,int i,int n[],int &max)

{

if(b!=NULL)

{

n[++i]++;//++i表示逐层递增，在每一层上的扫描每个叶子节点

if(n[i]>max) max=n[i];//max表示最大宽度

if(b->lchild!=NULL)

BTWidth(b->lchild,i,n,max);

if(b->rchild!=NULL)

BTWidth(b->rchild,i,n,max);

}

}

void main()

{

BTnode *b;

char *str="a(b(,e(j,k)),c(f,g))";

int a,lf,c;

int i=0,n[15]={0},max=0;

CreateBTnode(b,str);

printf("输出二叉树为:");

DispBTnode(b);

printf("\n");

a=BTnodeHeight(b);

printf("二叉树的高度为:%d\n",a);

lf=LeafNodes(b);

printf("二叉树的叶子节点个数为:%d\n",lf);

c=Nodes(b);

printf("二叉树的节点个数为:%d\n",c);

BTWidth(b,i,n,max);

printf("二叉树的宽度为:%d\n",max);

}

测试结果：

（二）哈夫曼实验设计思路：首先构造哈夫曼树和哈夫曼编码，在主函数里定义两个数组ht[]和hcd[]，分别用来存放哈夫曼树节点和哈夫曼编码，由于每个哈夫曼编码可能不一样长度，所以用start 指向每个哈夫曼编码的首位置，cd[start]~cd[n]表示存放其中的各个哈夫曼编码。输出初态之前要先将字符和权值初始化，然后输出初态和终态，最后用ch[]数组承接，输出由以上字符构成的字符串，，终态用for 循环输出，hcd[i].cd[j]即每个编号为i 的哈夫曼编码。

源代码如下：

#include

#include

#define N 10//哈夫曼编码的个数

#define M 5

typedef struct

{

char data;//节点值

double weight;//权重

int parent;

int lchild;

int rchild;

}HTNode;//哈夫曼树节点

typedef struct

{

char cd[N];//存放当前节点的哈夫曼编码

int start;//cd[start]~cd[n](每个哈夫曼码都是从start~n)

}HCode;//哈夫曼编码节点

void CreateHT(HTNode ht[],int n)//构造哈夫曼树

{

int i,k,lnode,rnode;

double min1,min2;

for(i=0;i

ht[i].parent=ht[i].lchild=ht[i].rchild=-1;

for(i=n;i

{

min1=min2=32767;//lnode 和 rnode 为权值最小的两个节点位置

lnode=rnode=-1;

for(k=0;k

if (ht[k].parent==-1)//在还没构造二叉树的节点中查找

{

if (ht[k].weight

{

min2=min1;

rnode=lnode;

min1=ht[k].weight;

lnode=k;

}

else if(ht[k].weight

{

min2=ht[k].weight;

rnode=k;

}

}

ht[i].weight=ht[lnode].weight+ht[rnode].weight;

ht[i].lchild=lnode;

ht[i].rchild=rnode;//ht[i]作为双亲节点

ht[lnode].parent=ht[rnode].parent=i;

}}

void CreateHCode(HTNode ht[],HCode hcd[],int n)//哈夫曼编码

{

int i,f,c;

HCode hc;

for(i=0;i

{

hc.start=n;

c=i;

f=ht[i].parent;

while(f!=-1)

{

if( ht[f].lchild==c)

hc.cd[hc.start--]='0';

else

hc.cd[hc.start--]='1';

c=f;

f=ht[f].parent;

}

hc.start++;

hcd[i]=hc;

}}

void main()

{

HTNode ht[2*M-1];//定义一个有T 个节点的哈夫曼数组

HCode hcd[M];//定义一个含有M 个元素的哈夫曼编码数组

char ch[N];

int i,j,t;

for(i=0;i

{

ht[i].data=NULL;

ht[i].weight=0;

}

printf("输入字符、权值以及输出存放哈夫曼树的数组的初态和终态\n");

printf("输入%d个字符: \n",M);

for(i=0;i

scanf("%c",&ht[i].data);

printf("输入各字符的权值: \n");

for(i=0;i

scanf("%lf",&ht[i].weight);

CreateHT(ht,M);

printf("哈夫曼树初态为：\n节点编号 字符 权值\n");

for(i=0;i

printf("第%d个\t\t%c\t%2.2f\n",i,ht[i].data,ht[i].weight);

printf("哈夫曼树终态为：\n节点编号\t字符\t权值\t左孩子\t右孩子\t双亲\n");

for(i=0;i

printf("第%d个\t\t%c\t%2.2f\t%d\t%d\t%d\n",i,ht[i].data,ht[i].weight,ht[i].lchild,ht[i].rchild,ht[i].parent);

for(i=0;i

for(int j=0;j

hcd[i].cd[j]=NULL;

CreateHCode(ht,hcd,M);

for(i=0;i

{

printf("%c的哈夫曼编码是：",ht[i].data);

for(j=hcd[i].start;j

printf("%c",hcd[i].cd[j]);

printf("\n");

}

printf("----------输入由以上字符组成的字符串，对电文编码并输出:------------\n"); printf("请输入由以上字符组成的字符串：\n");

scanf("%s",ch);

printf("该电文编码为：");

for(i=0;ch[i]!=NULL;i++)

{ for(j=0;j

if(ht[j].data==ch[i])

{

for(t=hcd[j].start;t

printf("%c",hcd[j].cd[t]);

}}

printf("\n");

}

操作结果：

四、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等） 注：内容一律使用宋体五号字，单倍行间距