实验六树.docx
《实验六树.docx》由会员分享，可在线阅读，更多相关《实验六树.docx（13页珍藏版）》请在冰点文库上搜索。
实验六树
实验六--树
实验六树
一．
1、参考工程shiyan6_1，请将其完善以实现树的基本运算。
若有一二叉树的括号表示为：
A（B（D，E（H（J，K（L，M（，N））），）），C（F，G（，I）））。
设计一个主程序实现如下功能，
（1）用二叉链表创建这棵二叉树T。
（2）输出二叉树T。
（3）分别输出二叉树T的先序、中序和后序遍历的序列。
（4）输出‘H’结点的左、右孩子结点值。
（5）输出二叉树T的深度。
（6）输出二叉树T的宽度。
（7）输出二叉树T的结点个数。
（8）输出二叉树T的叶子结点个数。
2【运行代码】
#define_Bitree_head
#include
usingnamespacestd;
typedefcharTElemType;
#defineMaxSize100
typedefstructBiTNode
{
TElemTypedata;
structBiTNode*lchild,*rchild;
}BiTNode,*BiTree;
intCreateBiTree（BiTree&T,char*str）;
voidPreOrder（BiTNode*b）;
BiTNode*FindNode（BiTNode*T,TElemTypex）;
voidDispBiTNode（BiTNode*T）;
intBiTNodeDepth（BiTNode*T）;
intBiTNodeWidth（BiTNode*T）;
intBiTNodes（BiTNode*T）;
#endif
BiTNode*FindNode（BiTNode*T,TElemTypex）
{
BiTNode*p;
if（T==NULL）
returnNULL;
elseif（T->data==x）
returnT;
else
{
p=FindNode（T->lchild,x）;
if（p!
=NULL）
returnp;
else
returnFindNode（T->rchild,x）;
}
}
voidDispBiTNode（BiTNode*T）
{
if（T!
=NULL）
{
cout<data;
if（T->lchild!
=NULL||T->rchild!
=NULL）
{
cout<<'（';
DispBiTNode（T->lchild）;
cout<<',';
DispBiTNode（T->rchild）;
cout<<'）';
}
}
}
intBiTNodeDepth（BiTNode*T）
{
intldepth,rdepth;
if（T==NULL）
return（0）;
else
{
ldepth=BiTNodeDepth（T->lchild）;
rdepth=BiTNodeDepth（T->rchild）;
return（ldepth>rdepth）?
（ldepth+1）:
（rdepth+1）;
}
}
intBiTNodeWidth（BiTNode*T）/*求¨®二t叉?
树º¡Âb的Ì?
宽¨ª度¨¨*/
{
struct
{
intlno;/*结¨¢点Ì?
的Ì?
层?
次ä?
编À¨¤号?
*/
BiTNode*p;/*结¨¢点Ì?
指?
针?
*/
}Qu[MaxSize];/*定¡§义°?
顺3序¨°非¤?
循-环¡¤队¨®列¢D*/
intfront,rear;/*定¡§义°?
队¨®首º¡Á和¨ª队¨®尾2指?
针?
*/
intlnum,max,i,n;
front=rear=0;/*置?
队¨®列¢D为a空?
队¨®*/
if（T!
=NULL）
{
rear++;
Qu[rear].p=T;/*根¨´结¨¢点Ì?
指?
针?
入¨?
队¨®*/
Qu[rear].lno=1;/*根¨´结¨¢点Ì?
的Ì?
层?
次ä?
编À¨¤号?
为a1*/
while（rear!
=front）/*队¨®列¢D不?
为a空?
*/
{
front++;
T=Qu[front].p;/*队¨®头ª¡¤出?
队¨®*/
lnum=Qu[front].lno;
if（T->lchild!
=NULL）/*左Á¨®孩¡é子Á¨®入¨?
队¨®*/
{
rear++;
Qu[rear].p=T->lchild;
Qu[rear].lno=lnum+1;
}
if（T->rchild!
=NULL）/*右®¨°孩¡é子Á¨®入¨?
队¨®*/
{
rear++;
Qu[rear].p=T->rchild;
Qu[rear].lno=lnum+1;
}
}
max=0;lnum=1;i=1;
while（i<=rear）
{
n=0;
while（i<=rear&&Qu[i].lno==lnum）
{
n++;i++;
}
lnum=Qu[i].lno;
if（n>max）max=n;
}
returnmax;
}
else
return0;
}
intBiTNodes（BiTNode*T）/*求¨®二t叉?
树º¡Âb的Ì?
结¨¢点Ì?
个?
数ºy*/
{
intnum1,num2;
if（T==NULL）
return0;
elseif（T->lchild==NULL&&T->rchild==NULL）
return1;
else
{
num1=BiTNodes（T->lchild）;
num2=BiTNodes（T->rchild）;
return（num1+num2+1）;
}
}
3【运行截图】
二．
1、编写工程shiyan6_2，实现构造一棵哈夫曼树，输出对应的哈夫曼编码和译码的算法。
并对下表的数据进行验证。
单词
The
of
a
to
and
in
that
he
is
at
on
for
His
are
be
出现频度
1192
677
541
518
462
450
242
195
190
181
174
157
138
124
123
2【运行代码】
#include"stdafx.h"
#include
#include
#defineN50
#defineMN*2-1
typedefstruct
{
chardata[5];
intweight;
intparent,lchild,rchild;
}HTNode;
typedefstruct
{
charcd[N];
intstart;
}HCode;
voidCreateHT（HTNodeht[],intn）
{
inti,k,lnode,rnode;
intmin1,min2;
for（i=0;i<2*n-1;i++）
ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
for（i=n;i<2*n-1;i++）
{
min1=min2=32767;
lnode=rnode=-1;
for（k=0;k<=i-1;k++）
if（ht[k].parent==-1）
{
if（ht[k].weight{
min2=min1;
rnode=lnode;
min1=ht[k].weight;
lnode=k;
}
elseif（ht[k].weight{
min2=ht[k].weight;
rnode=k;
}
}
ht[lnode].parent=ht[rnode].parent=i;
ht[i].weight=ht[lnode].weight+ht[rnode].weight;
ht[i].lchild=lnode;
ht[i].rchild=rnode;
}
}
voidCreateHCode（HTNodeht[],HCodehcd[],intn）
{
inti,f,c;
HCodehc;
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;
}
}
voidDispHCode（HTNodeht[],HCodehcd[],intn）
{
inti,k;
intsum=0,m=0,j;
printf（"输出哈夫曼编码:
\n"）;
for（i=0;i{
j=0;
printf（"%s:
\t",ht[i].data）;
for（k=hcd[i].start;k<=n;k++）
{
printf（"%c",hcd[i].cd[k]）;
j++;
}
m+=ht[i].weight;
sum+=ht[i].weight*j;
printf（"\n"）;
}
printf（"\n平均长度=%g\n",1.0*sum/m）;
}
intmain（）
{
intn=15,i;
char*str[]={
"The","of","a","to","and","in","that","he","is","at","on","for","His","are","be"
};
intfnum[]={
1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123
};
HTNodeht[M];
HCodehcd[N];
for（i=0;i{
strcpy（ht[i].data,str[i]）;
ht[i].weight=fnum[i];
}
printf（"\n"）;
CreateHT（ht,n）;
CreateHCode（ht,hcd,n）;
DispHCode（ht,hcd,n）;
printf（"\n"）;
return0;
}。
【运行结果截图】
三【个人总结】
每次编程的时候都是一种煎熬，编的时候写代码改错。
调试，尤其在调试的时候，会让你原本很好的心情一下子会变得很糟很糟，一次一次的调一次一次的不给运行，真的有想把电脑砸了的冲动，但我还是静下心来一次一次的调试一次一次的改错，忍着既然选择了这条路
就应该坚持下去，再苦再累也要坚持，不抛弃不放弃只要坚持总有一天会成功的，在一次一次的调试几乎绝望的时候当突然看到看个黑色屏幕时心情，一下子就豁然了，一切一切的付出都值得，编完收拾东西吃出好好的奖励自己一下，好好的吃一顿，付出的一切都值得，只要坚持，不抛弃不放弃就一定能成功。
胜利属于坚持的人！
！
！
！
！
！
！
！
！
！
！
升级会员 