数据结构二叉树的递归算法试验报告讲解

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）二叉树的高度：首先判断二叉树是否为空，若为空则此二

4、叉树高度为0, 。否则，就先分别求出左右子树的深度进行比较，取较大的树加一即为所求。（4）二叉树的度为 2 的结点个数：计算有左右孩子的结点个数，即为度为 2的结点个数。 三编程过程中遇到的问题及解决办法（1）后续遍历的非递归函数涉及到回溯的方法，开始设计的方案想的太过于简单，所以 形成了死循环，总是在最后的节点处不停地循环，后改成回溯后，该问题得到解决。（ 2）计算二叉树中度为 2 的结点个数中，返回循环的时候不论根结点有没有左右子树， 但个人设计时， 根总是会将自己默认为有左右子树， 自行增加 1. 后在同学帮助下才看到自 己的这个失误。四程序的闪光点 （自我评价 ）1. 程序模块化，各个

5、函数分开描述，方便观察2. 关键处有注释3. 建立二叉树时，用先序提示输入，比较人性化。五程序源代码 （ 以文件为单位提供 ）#include#include#define Maxsize 100typedef struct TREEstruct TREE *lTree;山东轻工业学院实验报告（附页）struct TREE *rTree; char data;Tree;void InitTree(Tree*);/ 初始化树void CreatTree(Tree*);/ 创建二叉树void PreTraverse(Tree*);/ 先序遍历递归void PreOrderTraverse(Tree

6、*);/先序遍历非递归void 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(Tr

7、ee*tree);/ void main()int H,L;Tree tree;/ Tree m;InitTree(&tree);CreatTree(&tree);cout 先序遍历递归为 :;PreTraverse(&tree);/ 先序遍历递归cout 先序遍历非递归 :;PreOrderTraverse(&tree);/ 先序遍历非递归 coutendl;cout 中序遍历递归为 :;InTraverse(&tree);/ 中序遍历递归山东轻工业学院实验报告（附页）cout 中序遍历非递归 :;InOrderTraverse(&tree);/ 中序遍历非递归coutendl;cout 后

8、序遍历递归为 :;PostTraverse(&tree);/ 后序遍历递归cout 后序遍历非递归 :;LastOrderTraverse(&tree);/ 后序遍历非递归 coutendl;cout 树的深度为 :;H=DepthTree(&tree);coutHendl;cout 叶子结点个数 :;L=LeafsTree(&tree);coutLendl;cout 结点个数： ;coutNodesTree(&tree)endl;cout 度为二的结点个数 ;L=Twochild(&tree);coutLlTree=NULL;tree-rTree=NULL;tree-data=0;void

9、CreatTree(Tree *tree)/ 创建树int n=0,m=0,i=0;山东轻工业学院实验报告（附页）if(tree-data=0)couttree-data;cout 节点 datan;if(n=1)Tree *lTree=(Tree*)malloc(sizeof(Tree); tree-lTree=lTree;lTree-lTree=NULL;lTree-rTree=NULL;lTree-data=0; CreatTree(tree-lTree);：有）：cout 节点 datai;if(i=0);else if(i=1)Tree *rTree=(Tree*)malloc(si

10、zeof(Tree); tree-rTree=rTree;rTree-lTree=NULL; rTree-rTree=NULL;rTree-data=0;CreatTree(tree-rTree);else if(n=0)山东轻工业学院实验报告（附页）cout 节点 datam;if(m=0);else if(m=1)Tree *rTree=(Tree*)malloc(sizeof(Tree); tree-rTree=rTree;rTree-lTree=NULL; rTree-rTree=NULL;rTree-data=0; CreatTree(tree-rTree);void PreTrav

11、erse(Tree*tree)/ 先序遍历递归 if(tree!=NULL)coutdatalTree!=NULL)PreTraverse(tree-lTree); PreTraverse(tree-rTree);else if(tree-rTree!=NULL)PreTraverse(tree-rTree);else;山东轻工业学院实验报告（附页）先序遍历非递归void PreOrderTraverse(Tree *tree)/Tree *S80=NULL;int top =0;while (tree!=NULL)|(top)if (tree!=NULL)coutdatalTree;else

12、tree = Stop;top-;tree = tree-rTree;中序遍历递归void InTraverse(Tree *tree)/if(tree!=NULL)if(tree-lTree!=NULL)山东轻工业学院实验报告（附页）InTraverse(tree-lTree);coutdatarTree);else if(tree-rTree!=NULL)coutdatarTree);elsecoutdatalTree;else tree = Dtop; top-;山东轻工业学院实验报告（附页）coutdatarTree;void PostTraverse(Tree *tree)/ 后序遍

13、历递归if(tree!=NULL)if(tree-lTree!=NULL)PostTraverse(tree-lTree);PostTraverse(tree-rTree);coutdatarTree!=NULL)PostTraverse(tree-rTree);coutdata ;elsecoutdatalTree;if(top!=0)p=stacktop-rTree;if(p=NULL)coutdatarTree!=NULL)if(stacktop-rTree-data=stacktop+1-data) coutdatarTree;elsep=NULL;int DepthTree(Tree

14、 *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)/int num1,num2;if(tree=NULL)return 0;else if(tree-lTree=NULL&tree-rTree=NULL)return 1;elsenum1=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&tree-rTree=NULL)return 1;elsenum1=NodesTree(tree-lTree);num2=NodesTree(tree-rTree);return(num1+num2+1);int Twochild(Tree*tree)/度为 2 的int n=0;if(tre