树的基本操作及其应用.docx
- 文档编号:1805649
- 上传时间:2023-05-01
- 格式:DOCX
- 页数:7
- 大小:49.80KB
树的基本操作及其应用.docx
《树的基本操作及其应用.docx》由会员分享,可在线阅读,更多相关《树的基本操作及其应用.docx(7页珍藏版)》请在冰点文库上搜索。
树的基本操作及其应用
综合性设计性实验报告
专业:
电子商务班级:
组别:
2013——2014学年第一学期
课程名称
数据结构
指导教师
本组成员
学号姓名
实验地点
一号楼603
实验时间
2013-12-19
实验名称
树的基本操作及其应用
实验类型
验证性
实验环境:
windowsXP
实验内容:
1.定义数据类型。
2.实现构造二叉树函数。
3.实现各种遍历函数。
实验目的与要求:
要求学生熟悉二叉树的各种存储结构的特性,重点是二叉链表的存储及遍历,及应用遍历解决二叉树的相应计算。
设计思路:
(设计原理、设计方案及流程等)
1、首先用定义满二叉树的方法,构造二叉树函数;输入的形式和输入值的范围:
以字符形式按先序遍历输入
2、输出的形式:
依次按递归先序、中序、后序遍历结果输出
3、程序所能达到的功能:
从键盘接受输入(先序)进行遍历(先序、中序、后序),将遍历结果打印输。
4、 测试数据:
输入满二叉树ab00f00
输出先序:
abf
中序:
baf
后序:
bfa
关键技术分析:
1、首先,初始化空二叉树;用满二叉树先序建立一个二叉树。
2、用递归调用依次递归先序、中序、后序遍历结果输出;
3、利用栈来判断是否二叉树全部输出;
4、主函数的调用。
实验步骤:
//二叉树的遍历算法
//**姚慧娟
//**13-12-19
#include
#include
#defineCHAR
//为了增强程序的多功能,定义CHAR时,用字符的处理模式
//当CHAR没有被定义时,采用整数处理模式
//数据类型的定义
#ifdefCHAR
typedefchardatatype;
#else
typedefintdatatype;
#endif
typedefstructnode
{
datatypedata;
structnode*lchild,*rchild;
}bitree;
bitree*root;
intn;
charc;
//用满二叉树的方法创建二叉树
bitree*creat_preorder()
{
bitree*t;
datatypex;
#ifdefCHAR
printf("\n\t请输入字符,以0作为每个节点的结束标志:
");
scanf("%c",&x);
fflush(stdin);//清除缓冲区
while((c=getchar())!
='\n'&&c!
=EOF);//清除缓冲区另外的方法
if(x=='0')t=NULL;
#else
printf("\n\t\t请输入正整数以0作为结束标志:
");
scanf('%d',&x);
if(x==0)t=NULL;
#endif
else
{
t=(structnode*)malloc(sizeof(bitree));
t->data=x;
t->lchild=creat_preorder();
t->rchild=creat_preorder();
}
return(t);
}
//先序遍历算法
voidpreorder(bitree*t)
{
if(t!
=NULL)
{
n=n+1;
#ifdefCHAR
printf("\tdata[%2d]=%3c",n,t->data);
#else
printf("\tdata[%2d]=%3d",n,t->data);
#endif
if(n%5==0)
printf("\n");
preorder(t->lchild);
preorder(t->rchild);
}
}
//中序遍历算法
voidinorder(bitree*t)
{
if(t!
=NULL)
{
inorder(t->lchild);
n=n+1;
#ifdefCHAR
printf("\tdata[%2d]=%3c",n,t->data);
#else
printf("\tdata[%2d]=%3d",n,t->data);
#endif
if(n%5==0)
printf("\n");
inorder(t->rchild);
}
}
//后序遍历算法
voidpostorder(bitree*t)
{
if(t!
=NULL)
{
postorder(t->lchild);
postorder(t->rchild);
n=n+1;
#ifdefCHAR
printf("\tdata[%2d]=%3c",n,t->data);
#else
printf("\tdata[%2d]=%3d",n,t->data);
#endif
if(n%5==0)
printf("\n");
}
}
main()
{
bitree*bintree=creat_preorder();
printf("\n先根序列:
\n\n");
preorder(bintree);
n=0;
printf("\n中根序列:
\n\n");
inorder(bintree);
n=0;
printf("\n后根序列:
\n\n");
postorder(bintree);
n=0;
printf("\n");
}
实验分析:
(1)建立二叉树时,用到了满二叉树的构造方法,有点儿麻烦,有待进一步的改进;
(2)非递归后序遍历时,未考虑到所有条件,只考虑节点的左右结点是否为空,而未考虑结点是否是前一个遍历结点的根节点且不为空;
(3)用栈实现非递归遍历。
实验总结:
通过做这次实验,发现自己在数据结构这门课程中还有很多不足,有很多知识还没掌握实验的时候出现了很多错误,有很多知识还不能运用,最后在同学的帮助下,终于完成了任务。
因为以前的C语言没学好,这学期的数据结构感到学的时候有些吃力,在实验的时候,我所以的不足都体现出来了,如果没有同学的帮助,我程序中的问题可能
需要很长时间才会解决,所以以后还是要努力赶上来。
在这次实验中,我也得到了很多收获,比如链表的应用,以前总是弄不明白,通过这次实验,在链表这一方面我懂了很多,但还不能运用自如,需要更多的练习。
这次实验,对本学期所学习的内容也是一次巩固,让我加深了对学过知识的记忆。
总之,这次实验让我既发现了自身的很多不足,又增长了很多知识。
评语与成绩:
教师签名:
年月日
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基本 操作 及其 应用