树和二叉树实验报告Word下载.docx
- 文档编号:7925085
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:21
- 大小:30.04KB
树和二叉树实验报告Word下载.docx
《树和二叉树实验报告Word下载.docx》由会员分享,可在线阅读,更多相关《树和二叉树实验报告Word下载.docx(21页珍藏版)》请在冰点文库上搜索。
后序遍历左子树,
后序遍历右子树,
访问根结点
4、层次遍历算法:
采用一个队列q,先将二叉树根结点入队列,然后退队列,输出该结点;
若它有左子树,便将左子树根结点入队列;
若它有右子树,便将右子树根结点入队列,直到队列空为止。
因为队列的特点是先进后出,所以能够达到按层次遍历二叉树的目的。
五、程序清单
#include<
stdio.h>
stdlib.h>
#defineM100
typedefcharEtype;
//定义二叉树结点值的类型为字符型
typedefstructBiTNode//树结点结构
{
Etypedata;
structBiTNode*lch,*rch;
}BiTNode,*BiTree;
BiTreeque[M];
intfront=0,rear=0;
//函数原型声明
BiTNode*creat_bt1();
BiTNode*creat_bt2();
voidpreorder(BiTNode*p);
voidinorder(BiTNode*p);
voidpostorder(BiTNode*p);
voidenqueue(BiTree);
BiTreedelqueue();
voidlevorder(BiTree);
inttreedepth(BiTree);
voidprtbtree(BiTree,int);
voidexchange(BiTree);
intleafcount(BiTree);
voidpaintleaf(BiTree);
BiTNode*t;
intcount=0;
//主函数
voidmain()
{
charch;
intk;
do{
printf("
\n\n\n"
);
\n===================主菜单==================="
\n\n1.建立二叉树方法1"
\n\n2.建立二叉树方法2"
\n\n3.先序递归遍历二叉树"
\n\n4.中序递归遍历二叉树"
\n\n5.后序递归遍历二叉树"
\n\n6.层次遍历二叉树"
\n\n7.计算二叉树的高度"
\n\n8.计算二叉树中叶结点个数"
\n\n9.交换二叉树的左右子树"
\n\n10.打印二叉树"
\n\n0.结束程序运行"
\n============================================"
\n请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)"
scanf("
%d"
&
k);
switch(k)
{
case1:
t=creat_bt1();
break;
//调用性质5建立二叉树算法
case2:
printf("
\n请输入二叉树各结点值:
"
fflush(stdin);
t=creat_bt2();
//调用递归建立二叉树算法
case3:
if(t)
{printf("
先序遍历二叉树:
preorder(t);
\n"
}
elseprintf("
二叉树为空!
break;
case4:
中序遍历二叉树:
inorder(t);
case5:
后序遍历二叉树:
postorder(t);
case6:
层次遍历二叉树:
levorder(t);
二叉树为空!
case7:
二叉树的高度为:
treedepth(t));
case8:
二叉树的叶子结点数为:
%d\n"
leafcount(t));
二叉树的叶结点为:
paintleaf(t);
case9:
交换二叉树的左右子树:
exchange(t);
prtbtree(t,0);
case10:
逆时针旋转90度输出的二叉树:
case0:
exit(0);
}//switch
}while(k>
=1&
&
k<
=10);
\n再见!
按回车键,返回…\n"
ch=getchar();
}//main
//利用二叉树性质5,借助一维数组V建立二叉树
BiTNode*creat_bt1()
{BiTNode*t,*p,*v[20];
inti,j;
Etypee;
/*输入结点的序号i、结点的数据e*/
\n请输入二叉树各结点的编号和对应的值(如1,a):
scanf("
%d,%c"
i,&
e);
while(i!
=0&
e!
='
#'
)//当i为0,e为'
时,结束循环
p=(BiTNode*)malloc(sizeof(BiTNode));
p->
data=e;
lch=NULL;
rch=NULL;
v[i]=p;
if(i==1)
t=p;
//序号为1的结点是根
else
j=i/2;
if(i%2==0)v[j]->
lch=p;
//序号为偶数,作为左孩子
elsev[j]->
rch=p;
//序号为奇数,作为右孩子
\n请继续输入二叉树各结点的编号和对应的值:
}
return(t);
}//creat_bt1;
//模仿先序递归遍历方法,建立二叉树
BiTNode*creat_bt2()
BiTNode*t;
Etypee;
%c"
if(e=='
)t=NULL;
//对于'
值,不分配新结点
else{
t=(BiTNode*)malloc(sizeof(BiTNode));
t->
lch=creat_bt2();
//左孩子获得新指针值
rch=creat_bt2();
//右孩子获得新指针值
}//creat_bt2
//先序递归遍历二叉树
voidpreorder(BiTNode*p)
{if(p){
%3c"
p->
data);
preorder(p->
lch);
rch);
}//preorder
//中序递归遍历二叉树
voidinorder(BiTNode*p)
inorder(p->
}//inorder
//后序递归遍历二叉树
voidpostorder(BiTNode*p)
{if(p){postorder(p->
postorder(p->
}//postorder
voidenqueue(BiTreeT)
if(front!
=(rear+1)%M)
{rear=(rear+1)%M;
que[rear]=T;
BiTreedelqueue()
if(front==rear)returnNULL;
front=(front+1)%M;
return(que[front]);
voidlevorder(BiTreeT)//层次遍历二叉树
BiTreep;
if(T)
{enqueue(T);
while(front!
=rear){
p=delqueue();
%3d"
if(p->
lch!
=NULL)enqueue(p->
rch!
inttreedepth(BiTreebt)//计算二叉树的高度
inthl,hr,max;
if(bt!
=NULL)
{hl=treedepth(bt->
hr=treedepth(bt->
max=(hl>
hr)?
hl:
hr;
return(max+1);
elsereturn(0);
voidprtbtree(BiTreebt,intlevel)//逆时针旋转90度输出二叉树树形
{intj;
if(bt)
{prtbtree(bt->
rch,level+1);
for(j=0;
j<
=6*level;
j++)printf("
"
%c\n"
bt->
prtbtree(bt->
lch,level+1);
voidexchange(BiTreebt)//交换二叉树左右子树
{BiTreep;
{p=bt->
lch;
bt->
lch=bt->
rch;
exchange(bt->
intleafcount(BiTreebt)//计算叶结点数
if(bt!
{leafcount(bt->
leafcount(bt->
if((bt->
lch==NULL)&
(bt->
rch==NULL))
count++;
return(count);
voidpaintleaf(BiTreebt)//输出叶结点
{if(bt!
{if(bt->
lch==NULL&
rch==NULL)
paintleaf(bt->
图11.2所示二叉树的输入数据顺序应该是:
abd#g###ce#h##f##。
图11.2二叉树示意图
运行结果:
===================主菜单===================
1.建立二叉树方法1
2.建立二叉树方法2
3.先序递归遍历二叉树
4.中序递归遍历二叉树
5.后序递归遍历二叉树
6.层次遍历二叉树
7.计算二叉树的高度
8.计算二叉树中叶结点个数
9.交换二叉树的左右子树
10.打印二叉树
0.结束程序运行
============================================
请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)1
请输入二叉树各结点的编号和对应的值(如1,a):
1,a
请继续输入二叉树各结点的编号和对应的值:
2,b
3,c
4,d
6,e
7,f
9,g
13,h
0,#
===================主菜单==================="
请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)3
先序遍历二叉树:
abdgcehf
请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)4
中序遍历二叉树:
dgbaehcf
请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)5
后序遍历二叉树:
gdbhefca
请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)6
9798
请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)7
4
请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)8
3
ghf
请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)9
d
g
b
a
e
h
c
f
请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)10
请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)2
请输入二叉树各结点值:
abd#g###ce#h##f##
请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)0
请按任意键继续...
6、调试心得及收获
建立二叉树有两种方法:
一种方法是利用二叉树的性质5来建立二叉树;
建立后,通过先序、中序、后序遍历,对二叉树有了进一步的理解与掌握。
对二叉树中各种计算也更了解了!
7、其他所想到的
一个二叉树,有许多部分构成,每一个部分都需要精心编写,才能对其进行操作,不至于出错。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉 实验 报告