《数据结构二叉树的递归算法实验报告》由会员分享，可在线阅读，更多相关《数据结构二叉树的递归算法实验报告（13页珍藏版）》请在金锄头文库上搜索。
1、齐鲁工业大学实验报告成绩课程名称数据结构指导教师单健芳实验日期院（系）信息学院专业班级计科（嵌入） 14-1 实验地点学生姓名高晨悦学号 201403071007 同组人无实验项目名称二叉树的递归算法一、实验目的和要求1. 实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。2. 求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。二、实验环境微型计算机 vc 6.0 三、实验内容1. 实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。2. 求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2 的结点个数。四、实验步骤一实验内容1. 实现二叉树的先序，中序与后序遍历的
2、递归算法与非递归算法。2. 求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2 的结点个数。二程序的设计思想1 实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。先构造二叉树，根据先序遍历的思想，输入根后，再输入左子树，直至左子树为空则 输入上一层右字树。（1）二叉树的非递归遍历是用显示栈来存储二叉树的结点指针，先序遍历时，按二叉 树前序遍历的顺序访问结点，并将结点的指针入栈，直到栈顶指针指向结点的左指针域为 空时取出栈顶指针并删除栈顶指针，访问刚取出的指针指向的结点的右指针指向的结点并 将其指针入栈，如此反复执行则为非递归操作。（2）二叉树的递归遍历：若二叉树为空，则空操作先序遍历
3、：（a）访问根结点；（b）先序遍历左子树；（c）先序遍历右子树。山东轻工业学院实验报告（附页）中序遍历：（a）中序遍历左子树；（b）访问根结点；（c）中序遍历右子树后序遍历：（a）后序遍历左子树；（b）后序遍历右子树；（c）访问根结点。2. 求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2 的结点个数。（1）求二叉树的叶子结点个数：先分别求得左右子树中个叶子结点的个数，再计算 出两者之和即为二叉树的叶子结点数。（2）二叉树的结点个数之和：先分别求得左子树右子树中结点之和，再计算两者之 和即为所求。（3）二叉树的高度：首先判断二叉树是否为空，若为空则此二叉树高度为0, 。否则， 就先分别求
4、出左右子树的深度进行比较，取较大的树加一即为所求。（4）二叉树的度为 2 的结点个数：计算有左右孩子的结点个数，即为度为2 的结点个数。三编程过程中遇到的问题及解决办法（1）后续遍历的非递归函数涉及到回溯的方法，开始设计的方案想的太过于简单，所以 形成了死循环，总是在最后的节点处不停地循环，后改成回溯后，该问题得到解决。（2）计算二叉树中度为2 的结点个数中，返回循环的时候不论根结点有没有左右子树， 但个人设计时， 根总是会将自己默认为有左右子树，自行增加 1. 后在同学帮助下才看到自 己的这个失误。四程序的闪光点 (自我评价 ) 1. 程序模块化，各个函数分开描述，方便观察2. 关键处有注释
5、3. 建立二叉树时，用先序提示输入，比较人性化。五程序源代码 ( 以文件为单位提供 ) #include #include #define Maxsize 100 typedef struct TREE struct TREE *lTree; 山东轻工业学院实验报告（附页）struct TREE *rTree; char data; Tree; void InitTree(Tree*);/初始化树void CreatTree(Tree*);/创建二叉树void PreTraverse(Tree*);/先序遍历递归void PreOrderTraverse(Tree*);/先序遍历非递归void
6、 InTraverse(Tree *tree);/中序遍历递归void InOrderTraverse(Tree *tree);/中序遍历非递归void PostTraverse(Tree *tree);/后序遍历递归void LastOrderTraverse(Tree *tree);/后序遍历非递归int DepthTree(Tree *tree);/计算树的深度int LeafsTree(Tree *tree);/计算叶子结点个数int NodesTree(Tree *tree);/计算结点个数int Twochild(Tree*tree);/计算度为二的结点个数void main()
7、int H,L; Tree tree; / Tree m; InitTree( CreatTree( coutlTree=NULL; tree-rTree=NULL; tree-data=0; void CreatTree(Tree *tree)/创建树 int n=0,m=0,i=0; 山东轻工业学院实验报告（附页）if(tree-data=0) couttree-data; coutdatan; if(n=1) Tree *lTree=(Tree*)malloc(sizeof(Tree); tree-lTree=lTree; lTree-lTree=NULL; lTree-rTree=NU
8、LL; lTree-data=0; CreatTree(tree-lTree); coutdatai; if(i=0); else if(i=1) Tree *rTree=(Tree*)malloc(sizeof(Tree); tree-rTree=rTree; rTree-lTree=NULL; rTree-rTree=NULL; rTree-data=0; CreatTree(tree-rTree); else if(n=0) 山东轻工业学院实验报告（附页） coutdatam; if(m=0); else if(m=1) Tree *rTree=(Tree*)malloc(sizeof(
9、Tree); tree-rTree=rTree; rTree-lTree=NULL; rTree-rTree=NULL; rTree-data=0; CreatTree(tree-rTree); void PreTraverse(Tree*tree)/先序遍历递归 if(tree!=NULL) coutdatalTree!=NULL) PreTraverse(tree-lTree); PreTraverse(tree-rTree); else if(tree-rTree!=NULL) PreTraverse(tree-rTree); else; 山东轻工业学院实验报告（附页） void Pre
10、OrderTraverse(Tree *tree)/先序遍历非递归 Tree *S80=NULL; int top =0; while (tree!=NULL)|(top) if (tree!=NULL) coutdatalTree; else tree = Stop; top-; tree = tree-rTree; void InTraverse(Tree *tree)/中序遍历递归 if(tree!=NULL) if(tree-lTree!=NULL) 山东轻工业学院实验报告（附页） InTraverse(tree-lTree); coutdatarTree); else if(tree
11、-rTree!=NULL) coutdatarTree); else coutdatalTree; else tree = Dtop; top-; 山东轻工业学院实验报告（附页）coutdatarTree; void PostTraverse(Tree *tree)/后序遍历递归 if(tree!=NULL) if(tree-lTree!=NULL) PostTraverse(tree-lTree); PostTraverse(tree-rTree); coutdatarTree!=NULL) PostTraverse(tree-rTree); coutdatadatalTree; if(to
12、p!=0) p=stacktop-rTree; if(p=NULL) coutdatarTree!=NULL) if(stacktop-rTree-data=stacktop+1-data) coutdatarTree; else p=NULL; int DepthTree(Tree *tree) /深度函数 int u,v; if (tree=NULL) return 0; u=DepthTree(tree-lTree); v=DepthTree(tree-rTree); if (uv) return (u+1); return (v+1); int LeafsTree(Tree *tree
13、)/子叶个数函数 int num1,num2; if(tree=NULL) return 0; else if(tree-lTree=NULL else num1=LeafsTree(tree-lTree); num2=LeafsTree(tree-rTree); return(num1+num2); 山东轻工业学院实验报告（附页） int NodesTree(Tree *tree)/结点个数函数 int num1,num2; if(tree=NULL) return 0; if(tree-lTree=NULL else num1=NodesTree(tree-lTree); num2=Nod
14、esTree(tree-rTree); return(num1+num2+1); int Twochild(Tree*tree)/度为 2 的 int n=0; if(tree=NULL) return(0); if(tree-lTree!=NULL return(Twochild(tree-lTree)+Twochild(tree-rTree)+n); 山东轻工业学院实验报告（附页）五、讨论、心得通过这次实验使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论， 才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。
