数据结构二叉树实验报告Word文档下载推荐.docx
- 文档编号:5272887
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:21
- 大小:93.21KB
数据结构二叉树实验报告Word文档下载推荐.docx
《数据结构二叉树实验报告Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《数据结构二叉树实验报告Word文档下载推荐.docx(21页珍藏版)》请在冰点文库上搜索。
康凯:
二叉树的显示输出及顺序栈的操作
岳晓芳:
二叉树的非递归遍历以及程序的调试
5、实验程序代码
#include<
iostream.h>
stdio.h>
string>
stdlib.h>
malloc.h>
constintN=100;
intm=0;
typedefstructNode
{
chardata;
intmark;
//标注从左还是右回来的
intcount;
//标记是否读过
structNode*Lchild;
structNode*Rchild;
}BiTNode,*BiTree;
//顺序栈的操作
typedefstruct{
BiTNodedata[N];
inttop;
}sqstack;
voidpush(sqstack&
s,BiTNodee)//入栈
{
if(s.top==N-1)
printf("
栈满\n"
);
//判栈满
else
{
s.top++;
s.data[s.top]=e;
}
}
voidpop(sqstack&
s)//出栈
if(s.top==-1)
栈空!
"
//判栈空
s.top--;
//二叉树的操作
voidCreate(BiTree&
T)//二叉树的建立
charch;
getchar();
ch=getchar();
if(ch=='
#'
)
T=NULL;
T=(BiTNode*)malloc(sizeof(BiTNode));
if(T==NULL)
printf("
error!
T->
data=ch;
请输入%c结点的左子树:
T->
data);
Create(T->
Lchild);
请输入%c结点的右子树:
Rchild);
}
voidpreorder(BiTreeT)//先序遍历
if(T==NULL)return;
if(T!
=NULL)
%c"
preorder(T->
voidpostorder(BiTreeT)//后序遍历
postorder(T->
voidinorder(BiTreeT)//中序遍历
inorder(T->
voidBiTreeleaf(BiTreeT)//求二叉树的叶子结点
if(T->
Lchild==NULL&
&
T->
Rchild==NULL)
{
m++;
}
BiTreeleaf(T->
intTreehigh(BiTree&
T)//求树高
intLH=0,RH=0;
if(T==NULL)return0;
LH=Treehigh(T->
RH=Treehigh(T->
if(LH>
RH)returnLH+1;
else
returnRH+1;
//非递归方法先序遍历二叉树
voidstackpreorder(BiTreeT)
sqstacks;
//栈的初始化
s.top=-1;
mark=0;
count=0;
//标记未读
push(s,*T);
//树不空根结点入栈
BiTNode*p;
//工作指针
while(s.top!
=-1)//栈不空
p=&
s.data[s.top];
while(p)
if(p->
count==0)//未读
{
printf("
*p);
p->
count=1;
//标记已读
}
mark==2)
return;
else
if(p->
Lchild!
=NULL&
p->
mark==0)//左孩子入栈,直到走到尽头
{
p->
mark=1;
//表明从左进来的
Lchild->
push(s,*p->
p=&
}
else
break;
if(s.top!
=-1)
p=&
pop(s);
Rchild!
mark=2;
//从右进
push(s,*p->
//右孩子入栈
p=&
//非递归方法中序遍历二叉树
voidstackinorder(BiTreeT)
=NULL)//树不空根结点入栈
{
while((p=&
s.data[s.top])&
p)
mark==0)//表明还没走左的
{
//左孩子入栈,直到走到尽头
p->
{p->
break;
mark==1)//从左子回来,读出
pop(s);
//是从右进入的
//非递归方法后序遍历二叉树,与中序非常类似,是要判断从右子回来才输出
voidstackpostorder(BiTreeT)
{p=&
=NULL&
p->
mark==2)//从右子回来,才输出
}
//按竖向树状显示二叉树的树状结构
voidPrintTree(BiTreeT,intlayer)
inti;
PrintTree(T->
Rchild,layer+1);
for(i=0;
i<
layer;
i++)
printf("
"
%c\n\n"
Lchild,layer+1);
voidpre_order(BiTreeT)
intx;
\t\t*************************\n"
\t\t*1--递归先序遍历*\n"
\t\t*2--非递归先序遍历*\n"
请输入你的选项:
scanf("
%d"
&
x);
switch(x)
case1:
此二叉树的先序递归遍历是:
preorder(T);
break;
case2:
此二叉树的先序非递归遍历是:
stackpreorder(T);
default:
\n"
voidin_order(BiTreeT)
\t\t*1--递归中序遍历*\n"
\t\t*2--非递归中序遍历*\n"
此二叉树的中序递归遍历是:
inorder(T);
此二叉树的中序非递归遍历是:
stackinorder(T);
voidpost_order(BiTreeT)
\t\t*1--递归后序遍历*\n"
\t\t*2--非递归后序遍历*\n"
此二叉树的后序递归遍历是:
postorder(T);
此二叉树的后序非递归遍历是:
stackpostorder(T);
intmain()
BiTreeT=NULL;
intdep;
intlayer=0;
//层数
intx,y=1;
while(y)
\t\t二叉树子系统\n"
\t\t*1--建立一棵二叉树*\n"
\t\t*2--先序遍历二叉树*\n"
\t\t*3--中序遍历二叉树*\n"
\t\t*4--后序遍历二叉树*\n"
\t\t*5--二叉树的叶子数*\n"
\t\t*6--输出二叉树的深度*\n"
\t\t*7--显示二叉树*\n"
\t\t*0--返回*\n"
提示:
空用'
表示:
scanf("
switch(x)
case1:
system("
cls"
按先序序列输入:
请输入该树的根结点:
Create(T);
\n您的树已经建立好!
\n\n"
case2:
system("
pre_order(T);
case3:
system("
in_order(T);
case4:
post_order(T);
case5:
此二叉树的叶子结点为:
BiTreeleaf(T);
\n此二叉树的叶子结点数为:
%d\n"
m);
case6:
此二叉树的深度为:
dep=Treehigh(T);
dep);
case7:
此二叉树的显示如下:
PrintTree(T,layer);
case0:
y=0;
default:
return0;
6、测试结果
(主界面)
(以上为第一棵树的所有操作)
(第二棵树的部分操作)
7、实验结论
通过本次实验的学习,不仅巩固了以前学过的知识,而且对二叉树的操作有了深刻的理解,使每一位小组成员都收获了很多。
具体学习了二叉树的建立,递归以及非递归的遍历思想,同时对于以前学过的顺序栈的操作也进一步的复习,对自己的编程水平有了很大的提高。
在实验中我们也发现了自己很多的不足。
课本上学到的知识当变成具体的程序时,又会遇到很多的问题,调试程序中遇见了很多问题,但是在团队协作的乐趣中,我们不畏错误,尝试着修改分析。
这样的过程中,我们的各方面在不断的提高,相信我们小组会越做越好。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 二叉 实验 报告