当前位置:首页 >> 计算机软件及应用 >>

实验五 二叉树基本操作的编程实现实验报告


HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY

数据结构 实 验 报 告
这里一定填写清楚自己选 择的实验层次。 (基础、提 高或者挑战)

实验项目 学生姓名 完成日期 指导教师 实验成绩 评阅教师

实验五 朱忠栋

实验类别 学生学号 2014-12-16 付勇智 评阅日期

基础篇 20120231515

实验五 二叉树基本操作的编程实现
【实验目的】
内容:二叉树基本操作的编程实现 要求: 二叉树基本操作的编程实现(2学时,验证型),掌握二叉树的建立、遍历、插入、删除等基本操作的 编程实现,也可以进一步编程实现查找等操作,存储结构主要采用顺序或链接结构。也鼓励学生利用基本 操作进行一些应用的程序设计。

【实验性质】
验证性实验(学时数:2H)

【实验内容】
以下的选题都可以作为本次实验的推荐题目 1. 建立二叉树,并以前序遍历的方式将结点内容输出。 2. 将一个表示二叉树的数组结构转换成链表结构。 3. 将表达式二叉树方式存入数组,以递归方式建立表达式之二叉树状结构,再分别输出前序、中序 及后序遍历结果,并计算出表达式之结果。

【注意事项】
1.开发语言:使用C。 2.可以自己增加其他功能。

【实验分析、说明过程】
页面不够,可续页。 根据自己选择的层次不同的实验内容,完善程序代码,调试通过后,分析说明该问题处理的详细算法 过程。不需要写出详细的代码,只表达清楚详细的处理算法即可。可以采用流程图、形式语言或者其他数 学表达方式来说明。 这次实验考查的主要是:递归建立二叉树,递归输出先序,中序和后序遍历的结果;非递归建 立二叉树,再以非递归方式分别输出先序,中序和后序遍历的结果。 而对于基础篇考查的主要是:递归建立二叉树,递归输出先序,中序和后序遍历的结果,是以填 空的方式进行考查的。 对于第一空:递归实现的先序遍历,其实现方法是: printf("%d",p->data); if(p->lchild!=NULL) preorder(p->lchild); if(p->rchild!=NULL) preorder(p->rchild); 对于第二空:递归实现的中序遍历,其实现方法是: if(p->lchild!=NULL) inorder(p->lchild); 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 个结点的完全二叉树的 深度为 log2n +1 ! ! ! 二叉树的计算方法:若一棵二叉树为空,则其深度为 0,<WBR>否则其深度等于左子 树和右子树的最大深度加 1 2. 三种根序遍历主要思路是什么? 答:大体思路差不多,但节点访问位置不一样, 先序的话,是先访问,然后节点压栈,移到左子 树,至节点空退栈,移到右子树。 而中序的话,是先节点压栈,移到左子树,至节点空退栈,访 问节点,然后移到右子树。另外,所谓前序、中序、后序遍历,全称是前根序遍历,中根序遍历, 后根序遍历,不管哪种遍历,访问左子树 一定在 访问右子树之前,不同的就是根的访问时机。 所以三种递归/或非递归,程序思路都是一样的。 3. 如果不用遍历算法一般启用什么数据结构实现后序遍历? 答:用栈实现后序遍历。 4. 举出二叉树的应用范例? 答:一个集合的幂集、排列问题、组合问题

【实验小结】

(总结本次实验的重难点及心得、体会、收获)

页面不够,可续页。 在本次实验中我遇到了许多困难,终于我顺利地完成了它。本次实验我收获良多,不仅仅是书本上的 知识上的欠缺得到了补充,使我更好的掌握了本章的内容;在学习工作的品质方面也有了较大的进步。总 之这次实验,我认为是比较成功的。 在知识方面, 通过这次实验我对树的相关知识进行了进一步的思考, 使我对其有了全面而深入的认识, 对其特点和应用也有了相应的了解。 尤其是在应用方面使我不在像以前一样拘泥于学, 而忽视用的重要性。 一个合格的学习者,必定是一个善于学以致用的学习者,这样的学习者不仅仅会学习,还会用自己所学创 造价值,是自己所学的知识实现其应有的价值,而不是消化在肚子里。 在对今后发展方面,通过本次实验我明白了任何事都不是一蹴而就的,只有经过不断的钻研,反复的 实验改进才可能得到自己想要的结果。经历失败不可怕,可怕的是没有这个过程,只要有了这个过程,就 算一时没有成功,但是我相信最终一定会成功的。不是不会成功,只是还没有成功而已——你正在走向成 功的道路上。等经过了这一段探究的历程,你必定会获得你渴望已久的成功。

【附录-实验代码】

页面不够,可续页。 这个代码必须是调试通过,没有问题的最终代码。 #include<stdio.h> #include<stdlib.h> #include<conio.h> #include<iostream.h> #define MAXSIZE 100 typedef char elemtype; typedef struct bitree { elemtype data; struct bitree *lchild,*rchild; }BTREE; BTREE *create() {//先序递归创建二叉树 char ch; BTREE *bt; ch=getchar(); if(ch=='#') bt=NULL; else { bt=(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) { printf("%d",p->data); if(p->lchild!=NULL) if(p->rchild!=NULL) } } void inorder(BTREE *root) {//递归实现的中序遍历 BTREE *p;

preorder(p->lchild); preorder(p->rchild);

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!=NULL) printf("%d",p->data); } }

inorder(p->lchild); inorder(p->rchild);

postorder(p->lchild); postorder(p->rchild);

void lorder(BTREE *root) {//非递归实现的层次遍历 BTREE *q[MAXSIZE],*p; // maxsize 为最大容量 int f,r; // f,r 类似于头尾指针 q[1]=root; f=r=1; while(f<=r) { p=q[f]; f++; //出队 printf("%c",p->data); if(p->lchild!=NULL) { r++; q[r]=p->lchild; } //入队 if(p->rchild!=NULL) { r++; q[r]=p->rchild; } //入队 } } void showmenu()

{//显示菜单 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) { case 1:printf("请按先序依次输入二叉树的结点,\n"); printf("空结点用#号表示.\n"); root=create(); printf("二叉树创建成功,按任意键继续…\n"); 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"); system("pause"); system("cls");

break; case 5:printf("二叉树层次遍历结果为:\n"); lorder(root); printf("\n"); system("pause"); system("cls"); break; case 6:return; default: printf("你的输入有误,请从新输入!\n"); system("pause"); system("cls"); } } }


相关文章:
实验五
HUBEIUNIVERSITY OF AUTOMOTIVE TECHNOLOGY 数据结构 实验 报告实验项目 学生姓名 ...实验五 二叉树基本操作的编程实现【实验目的】内容:二叉树基本操作的编程实现 ...
实验五 二叉树基本操作的编程实现
实验五 二叉树基本操作的编程实现实验目的】 实验目的】内容:二叉树基本操作的编程实现 要求: 二叉树基本操作的编程实现(2学时,验证型),掌握二叉树的建立、遍历...
实验五 二叉树的遍历
目的: 掌握队列的特点和队列的基本操作要求: 熟练掌握顺序队列的建立、入队、出...实现二叉树的遍历 实验设备(环境): VC++6.0 实验内容: 1、 分析、理解程序...
实验5 二叉搜索树的基本操作(大作业)
浙江大学城市学院实验报告课程名称 实验项目名称 学生姓名 实验成绩 实验五 数据...请编写程序实现二叉搜索树的下述基本操作: ① 初始化该二叉搜索树 void Init...
实验五 二叉树的基本操作
实验五 二叉树的基本操作 - 山东英才学院 实验报告 课 学院(系) 班 姓名 年 学号 成绩: 月日 实验题目: 实验题目: 一、实验目的和要求 二叉树是数据结构...
《数据结构》实验提示_实验5_二叉树的基本操作和应用
《数据结构》实验提示_实验5_二叉树的基本操作和应用_化学_自然科学_专业资料。《数据结构》实验提示 实验五二叉树的基本操作和应用(1)先定义宏,再定义元素、二...
数据结构实验五 二叉树及其应用
计算机系数据结构实验报告(5)实验目的:树是数据结构...掌握二叉树的各种存储结构和熟悉对二叉树的基本操作...实验内容和过程:源程序: #include<iostream> #...
实验5:二叉树的创建、遍历及其它基本操作的实现 - 副本
实验5:二叉树的创建、遍历及其它基本操作的实现 - 副本_计算机硬件及网络_IT/计算机_专业资料。实验 5:二叉树的创建、遍历及其它基本操作的实现实验所需 学时数...
数据结构实验五二叉树的创建与遍历
数据结构实验五二叉树的创建与遍历 - 实验五 二叉树的创建与遍历 实验目的: 通过上机实验进一步掌握栈、队列、二叉树的存储结构及基本操作的实现方法。 实验内容与...
数据结构实验五B
数据结构实验五B_数学_自然科学_专业资料。《数据结构与算法分析》 实验报告书 ...实现程序,构造二叉树的链式存储结构,并完成递归先序、中序、后序遍历操作。 二...
更多相关标签: