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

HUBEIUNIVERSITYOFAUTOMOTIVETECHNOLOGY数据结构实验报告实验项目实验五实验类别基础篇学生姓名朱忠栋学生学号20120231515完成日期2014-12-16指导教师付勇智实验成绩评阅日期评阅教师这里一定填写清楚自己选择的实验层次。（基础、提高或者挑战）实验五二叉树基本操作的编程实现【实验目的】内容：二叉树基本操作的编程实现要求：二叉树基本操作的编程实现（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否则其深度等于左子树和右子树的最大深度加12.三种根序遍历主要思路是什么？答：大体思路差不多，但节点访问位置不一样，先序的话，是先访问，然后节点压栈，移到左子树，至节点空退栈，移到右子树。而中序的话，是先节点压栈，移到左子树，至节点空退栈，访问节点，然后移到右子树。另外，所谓前序、中序、后序遍历，全称是前根序遍历，中根序遍历，后根序遍历，不管哪种遍历，访问左子树一定在访问右子树之前，不同的就是根的访问时机。所以三种递归/或非递归，程序思路都是一样的。3.如果不用遍历算法一般启用什么数据结构实现后序遍历？答：用栈实现后序遍历。4.举出二叉树的应用范例？答：一个集合的幂集、排列问题、组合问题【实验小结】(总结本次实验的重难点及心得、体会、收获)页面不够，可续页。在本次实验中我遇到了许多困难，终于我顺利地完成了它。本次实验我收获良多，不仅仅是书本上的知识上的欠缺得到了补充，使我更好的掌握了本章的内容；在学习工作的品质方面也有了较大的进步。总之这次实验，我认为是比较成功的。在知识方面，通过这次实验我对树的相关知识进行了进一步的思考，使我对其有了全面而深入的认识，对其特点和应用也有了相应的了解。尤其是在应用方面使我不在像以前一样拘泥于学，而忽视用的重要性。一个合格的学习者，必定是一个善于学以致用的学习者，这样的学习者不仅仅会学习，还会用自己所学创造价值，是自己所学的知识实现其应有的价值，而不是消化在肚子里。在对今后发展方面，通过本次实验我明白了任何事都不是一蹴而就的，只有经过不断的钻研，反复的实验改进才可能得到自己想要的结果。经历失败不可怕，可怕的是没有这个过程，只要有了这个过程，就算一时没有成功，但是我相信最终一定会成功的。不是不会成功，只是还没有成功而已——你正在走向成功的道路上。等经过了这一段探究的历程，你必定会获得你渴望已久的成功。【附录-实验代码】页面不够，可续页。这个代码必须是调试通过，没有问题的最终代码。#includestdio.h#includestdlib.h#includeconio.h#includeiostream.h#defineMAXSIZE100typedefcharelemtype;typedefstructbitree{elemtypedata;structbitree*lchild,*rchild;}BTREE;BTREE*create(){//先序递归创建二叉树charch;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);}voidpreorder(BTREE*root){//递归实现的先序遍历BTREE*p;p=root;if(p!=NULL){printf(%d,p-data);if(p-lchild!=NULL)preorder(p-lchild);if(p-rchild!=NULL)preorder(p-rchild);}}voidinorder(BTREE*root){//递归实现的中序遍历BTREE*p;p=root;if(p!=NULL){if(p-lchild!=NULL)inorder(p-lchild);printf(%d,p-data);if(p-rchild!=NULL)inorder(p-rchild);}}voidpostorder(BTREE*root){//递归实现的后序遍历BTREE*p;p=root;if(p!=NULL){if(p-lchild!=NULL)postorder(p-lchild);if(p-rchild!=NULL)postorder(p-rchild);printf(%d,p-data);}}voidlorder(BTREE*root){//非递归实现的层次遍历BTREE*q[MAXSIZE],*p;//maxsize为最大容量intf,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;}//入队}}voidshowmenu(){//显示菜单printf(欢迎使用二叉树操作演示软件\n);printf(\t1、创建二叉树\n);printf(\t2、先序遍历二叉树\n);printf(\t3、中序遍历二叉树\n);printf(\t4、后序遍历二叉树\n);printf(\t5、层次遍历二叉树\n);printf(\t6、退出程序\n);}voidmain(){BTREE*root=NULL;intno;while(1){showmenu();printf(请输入你的选择：);scanf(%d,&no);fflush(stdin);//清除键盘缓冲区switch(no){case1:printf(请按先序依次输入二叉树的结点，\n);printf(空结点用#号表示.\n);root=create();printf(二叉树创建成功，按任意键继续…\n);getch();system(cls);break;case2:printf(二叉树先序遍历结果为：\n);preorder(root);printf(\n);system(pause);system(cls);break;case3:printf(二叉树中序遍历结果为：\n);inorder(root);printf(\n);system(pause);system(cls);break;case4:printf(二叉树后序遍历结果为：\n);postorder(root);printf(\n);system(pause);system(cls);break;case5:printf(二叉树层次遍历结果为：\n);lorder(root);printf(\n);system(pause);system(cls);break;case6:return;default:printf(你的输入有误，请从新输入！\n);system(pause);system(cls);}}}