实验五 二叉树基本操作的编程实现.doc

HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY数据结构实 验 报 告实验项目实验五实验类别基础篇学生姓名学生学号完成日期2016-11-19指导教师袁科实验成绩评阅日期评阅教师实验五 二叉树基本操作的编程实现【实验目的】内容：二叉树基本操作的编程实现要求：二叉树基本操作的编程实现（2学时，验证型），掌握二叉树的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找等操作，存储结构主要采用顺序或链接结构。也鼓励学生利用基本操作进行一些应用的程序设计。【实验性质】验证性实验（学时数：2H）【实验内容】以下的选题都可以作为本次实验的推荐题目1. 建立二叉树，并以前序遍历的方式将结点内容输出。2. 将一个表示二叉树的数组结构转换成链表结构。3. 将表达式二叉树方式存入数组，以递归方式建立表达式之二叉树状结构，再分别输出前序、中序及后序遍历结果，并计算出表达式之结果。【实验分析、说明过程】 这次实验主要是对二叉树基本操作的编程实现。通过递归输出先序遍历，中序遍历，后序遍历的结果。二叉树中常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理，这就需要遍历二叉树。即要求按某条路径寻访树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。回顾二叉树的递归定义可知，二叉树是由3个基本单元组成：根节点、左子树和右子树。因此，若能依次遍历这三部分，便是遍历了整棵二叉树。如果以L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则可有DLR、LDR、LRD、DRL、RDL、RLD这6种遍历二叉树的方案。我们此次实验主要是通过前序遍历DLR、中序遍历LRD以及后续遍历LDR。基于二叉树的递归定义，可得下述遍历二叉树的递归定义算法。先序遍历二叉树的操作定义：若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。所以此次实验所填代码：printf(%c,root-data );preorder(root-lchild ); preorder(root-rchild );中序遍历二叉树的操作定义：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。实验代码为：inorder(root-lchild );pr0intf(%c,root-data );inorder(root-rchild );后序遍历二叉树的操作定义：若二叉树为空，则空操作；否则；（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。postorder(root-lchild ) ;postorder(root-rchild ) ; printf(%c,root-data) ;4. 【思考问题】1、 二叉树是树吗？它的定义为什么是递归的？答：最多有两棵子树的有序树，称为二叉树。二叉树是一种特殊的树。二叉树的定义本来就是递归的，这样跟便于理解。二叉树的层次遍历不是递归，而使用的是队列。2、 三种根序遍历主要的思想是什么。答：大体思路差不多，但节点访问位置不一样，先序的话，是先访问，然后节点压栈，移到左子树，至节点空退栈，移到右子树。而中序的话，是先节点压栈，移到左子树，至节点空退栈，访问节点，然后移到右子树。另外，所谓前序、中序、后序遍历，全称是前根序遍历，中根序遍历，后根序遍历，不管哪种遍历，访问左子树一定在访问右子树之前，不同的就是根的访问时机。所以三种递归/或非递归，程序思路都是一样的。3、 如果不用遍历算法一般启用什么数据结构实现后序遍历的结果。答：后序遍历。4、 举例二叉树的应用范例。答：排列问题、组合问题。5. 【实验小结】 (总结本次实验的重难点及心得、体会、收获)这次实验的目的是对二叉树的编程基本实现。这次实验设计让我更加了解并更加灵活运用到大一学到的C程序设计和这个学期学到的数据结构。实验任务要求不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力。我做的是基础篇，填完那几处空是很简单的，但这样是不够的，还要很层次的理解其中的原理。这次实验的知识点有很多，比如这次实验就包含了先序遍历，中序遍历，后序遍历。在识方面，通过这次实验我对树的相关知识进行了进一步的思考，使我对其有了全面而深入的认识，对其特点和应用也有了相应的了解。尤其是在应用方面使我不在像以前一样拘泥于学，而忽视用的重要性。一个合格的学习者，必定是一个善于学以致用的学习者。【附录-实验代码】#include#include#include#include#define MAXSIZE 100typedef 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(%c,root-data );preorder(root-lchild ) ; preorder(root-rchild ) ; void inorder(BTREE *root)/递归实现的中序遍历 BTREE *p; p=root; if(p!=NULL) inorder(root-lchild ) ; printf(%c,root-data ) ; inorder(root-rchild ) ;void postorder(BTREE *root)/递归实现的后序遍历 BTREE *p; p=root;if(p!=NULL) postorder(root-lchild ) ; postorder(root-rchild ) ; printf(%c,root-data) ;void lorder(BTREE *root)/非递归实现的层次遍历 BTREE *qMAXSIZE,*p; / maxsize为最大容量 int f,r; / 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()/显示菜单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); s