试验五-二叉树基本操作的编程实现试验报告_第1页
试验五-二叉树基本操作的编程实现试验报告_第2页
试验五-二叉树基本操作的编程实现试验报告_第3页
试验五-二叉树基本操作的编程实现试验报告_第4页
试验五-二叉树基本操作的编程实现试验报告_第5页
已阅读5页,还剩4页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY数据结构实验报告这里一定填写清楚自己选 择的实验层次。 (基础、提 高或者挑战)实验项目实验五实验类别基础篇学生姓名朱忠栋学生学号1515完成日期2014-12-16指导教师付勇智实验成绩评阅日期评阅教师实验五 二叉树基本操作的编程实现【实验目的】内容:二叉树基本操作的编程实现要求:二叉树基本操作的编程实现( 2学时,验证型),掌握二叉树的建立、遍历、插入、删除等基本操作的 编程实现,也可以进一步编程实现查找等操作,存储结构主要采用顺序或链接结构。也鼓励学生利用基本 操作进行一些应用的程序设计。【实验性质】验证性

2、实验(学时数: 2H)【实验内容】以下的选题都可以作为本次实验的推荐题目1. 建立二叉树,并以前序遍历的方式将结点内容输出。2. 将一个表示二叉树的数组结构转换成链表结构。3. 将表达式二叉树方式存入数组,以递归方式建立表达式之二叉树状结构,再分别输出前序、中序 及后序遍历结果,并计算出表达式之结果。【注意事项】1. 开发语言:使用 C。2. 可以自己增加其他功能。【实验分析、说明过程】页面不够,可续页。根据自己选择的层次不同的实验内容,完善程序代码,调试通过后,分析说明该问题处理的详细算法 过程。不需要写出详细的代码,只表达清楚详细的处理算法即可。可以采用流程图、形式语言或者其他数 学表达方

3、式来说明。这次实验考查的主要是 :递归建立二叉树,递归输出先序,中序和后序遍历的结果;非递归建立二叉树,再以非递归方式分别输出先序,中序和后序遍历的结果。而对于基础篇 考查的主要是 :递归建立二叉树,递归输出先序,中序和后序遍历的结果,是以填 空的方式进行考查的。对于第一空:递归实现的先序遍历,其实现方法是:printf(%d,p-data);if(p-lchild!=NULL)preorder(p-lchild);if(p-rchild!=NULL)preorder(p-rchild);对于第二空:递归实现的中序遍历,其实现方法是:if(p-lchild!=NULL) inorder(p-l

4、child);printf(%d,p-data);if(p-rchild!=NULL)inorder(p-rchild);对于第三空:递归实现的后序遍历,其实现方法是:if(p-lchild!=NULL)postorder(p-lchild);if(p-rchild!=NULL)postorder(p-rchild);printf(%d,p-data);思考问题】页面不够,可续页。1. 二叉树是树吗?它的定义为什么是递归的?答:最多有两棵子树的有序树,称为 二叉树 。二叉树是一种特殊的 树。 具有 n个结点的完全二叉树的2. 三种根序遍历主要思路是什么?答: 大体思路差不多,但节点访问位置不一

5、样, 先序的话,是先访问,然后节点压栈,移到左子 树,至节点空退栈,移到右子树。 而中序的话,是先节点压栈,移到左子树,至节点空退栈,访 问节点,然后移到右子树。另外,所谓前序、中序、 后序遍历 ,全称是前根序遍历,中根序遍历, 后根序遍历,不管哪种遍历,访问左子树 一定在 访问右子树之前,不同的就是根的访问时机。 所以三种 递归 /或非递归,程序思路都是一样的 。3. 如果不用遍历算法一般启用什么数据结构实现后序遍历?答:用栈实现后序遍历。4. 举出二叉树的应用范例?答:一个集合的幂集、排列问题、组合问题【 实验小结 】 ( 总结本次实验的重难点及心得、体会、收获 )页面不够,可续页。在本次

6、实验中我遇到了许多困难,终于我顺利地完成了它。本次实验我收获良多,不仅仅是书本上的 知识上的欠缺得到了补充,使我更好的掌握了本章的内容;在学习工作的品质方面也有了较大的进步。总 之这次实验,我认为是比较成功的。在知识方面, 通过这次实验我对树的相关知识进行了进一步的思考,使我对其有了全面而深入的认识,对其特点和应用也有了相应的了解。 尤其是在应用方面使我不在像以前一样拘泥于学, 而忽视用的重要性。 一个合格的学习者,必定是一个善于学以致用的学习者,这样的学习者不仅仅会学习,还会用自己所学创 造价值,是自己所学的知识实现其应有的价值,而不是消化在肚子里。在对今后发展方面,通过本次实验我明白了任何

7、事都不是一蹴而就的,只有经过不断的钻研,反复的 实验改进才可能得到自己想要的结果。经历失败不可怕,可怕的是没有这个过程,只要有了这个过程,就 算一时没有成功,但是我相信最终一定会成功的。不是不会成功,只是还没有成功而已你正在走向成 功的道路上。等经过了这一段探究的历程,你必定会获得你渴望已久的成功。附录 -实验代码】页面不够,可续页。 这个代码必须是调试通过,没有问题的最终代码。 #include#include#include#include#define MAXSIZE 100 typedef char elemtype; typedef struct bitreeelemtype dat

8、a;struct bitree *lchild,*rchild;BTREE;BTREE *create()/ 先序递归创建二叉树char ch;BTREE *bt;ch=getchar();if(ch=#)bt=NULL;elsebt=(BTREE *)malloc(sizeof(BTREE); bt-data=ch;bt-lchild=create(); /递归创建左子树 bt-rchild=create(); / 递归创建右子树 return(bt);void preorder(BTREE *root)/ 递归实现的先序遍历BTREE *p;p=root; if(p!=NULL)print

9、f(%d,p-data);if(p-lchild!=NULL)preorder(p-lchild);if(p-rchild!=NULL)preorder(p-rchild);void inorder(BTREE *root)/ 递归实现的中序遍历BTREE *p;p=root;if(p!=NULL)if(p-lchild!=NULL)printf(%d,p-data);if(p-rchild!=NULL)void postorder(BTREE *root)/ 递归实现的后序遍历BTREE *p;p=root;if(p!=NULL)if(p-lchild!=NULL) if(p-rchild!

10、=NULL) printf(%d,p-data);void lorder(BTREE *root)/ 非递归实现的层次遍历BTREE *qMAXSIZE,*p; int f,r;q1=root;f=r=1;while(fdata); if(p-lchild!=NULL) r+; qr=p-lchild;/入队if(p-rchild!=NULL)r+;qr=p-rchild; / 入队void showmenu()inorder(p-lchild);inorder(p-rchild);postorder(p-lchild); postorder(p-rchild);/ maxsize 为最大容量

11、 / f,r 类似于头尾指针/出队/ 显示菜单printf( 欢迎使用二叉树操作演示软件 n);printf(t1 、创建二叉树 n);printf(t2 、先序遍历二叉树 n);printf(t3 、中序遍历二叉树 n);printf(t4 、后序遍历二叉树 n);printf(t5 、层次遍历二叉树 n); printf(t6 、退出程序 n);void main()BTREE *root=NULL;int no;while(1)showmenu();printf( 请输入你的选择: );scanf(%d,&no);fflush(stdin);/ 清除键盘缓冲区switch(no)n);c

12、ase 1:printf( 请按先序依次输入二叉树的结点, printf( 空结点用 #号表示 .n); root=create();n);printf( 二叉树创建成功,按任意键继续 getch();system(cls);break;case 2:printf( 二叉树先序遍历结果为: n); preorder(root); printf(n); system(pause); system(cls); break;case 3:printf( 二叉树中序遍历结果为: n); inorder(root); printf(n);system(pause); system(cls); break;case 4:printf( 二叉树后序遍历结果为: n); postorder(root); printf(n); sys

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论