数据结构二叉树的递归算法实验报告

.齐鲁工业大学实验报告 成绩 课程名称 数据结构 指导教师 单健芳 实验日期 院（系） 信息学院 专业班级 计科（嵌入）14-1 实验地点 学生姓名 高晨悦 学号 201403071007 同组人 无 实验项目名称 二叉树的递归算法 一、实验目的和要求1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。二、实验环境 微型计算机vc 6.0三、实验内容1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。四、实验步骤一实验内容1.实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。二程序的设计思想1实现二叉树的先序，中序与后序遍历的递归算法与非递归算法。先构造二叉树，根据先序遍历的思想，输入根后，再输入左子树，直至左子树为空则输入上一层右字树。（1）二叉树的非递归遍历是用显示栈来存储二叉树的结点指针，先序遍历时，按二叉树前序遍历的顺序访问结点，并将结点的指针入栈，直到栈顶指针指向结点的左指针域为空时取出栈顶指针并删除栈顶指针，访问刚取出的指针指向的结点的右指针指向的结点并将其指针入栈，如此反复执行则为非递归操作。（2）二叉树的递归遍历：若二叉树为空，则空操作先序遍历：（a）访问根结点； （b）先序遍历左子树；（c）先序遍历右子树。中序遍历 ：（a）中序遍历左子树； （b）访问根结点；（c）中序遍历右子树后序遍历： （a）后序遍历左子树； （b）后序遍历右子树； （c）访问根结点。2.求二叉树的结点个数，叶子结点个数，二叉树的高度，度为2的结点个数。（1）求二叉树的叶子结点个数：先分别求得左右子树中个叶子结点的个数，再计算出两者之和即为二叉树的叶子结点数。（2）二叉树的结点个数之和：先分别求得左子树右子树中结点之和，再计算两者之和即为所求。（3）二叉树的高度：首先判断二叉树是否为空，若为空则此二叉树高度为0,。否则，就先分别求出左右子树的深度进行比较，取较大的树加一即为所求。（4）二叉树的度为2的结点个数：计算有左右孩子的结点个数，即为度为2的结点个数。三编程过程中遇到的问题及解决办法（1）后续遍历的非递归函数涉及到回溯的方法，开始设计的方案想的太过于简单，所以形成了死循环，总是在最后的节点处不停地循环，后改成回溯后，该问题得到解决。（2）计算二叉树中度为2的结点个数中，返回循环的时候不论根结点有没有左右子树，但个人设计时，根总是会将自己默认为有左右子树，自行增加1.后在同学帮助下才看到自己的这个失误。四程序的闪光点(自我评价)1.程序模块化，各个函数分开描述，方便观察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*);/先序遍历非递归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(Tree*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后序遍历递归为:;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 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(sizeof(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 PreTraverse(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;elsetree = 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;elsetree = 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);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 *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; 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&tree-rTree=NULL) return 1; else num1=NodesTree(tree-lTree); num2=NodesTree(tree-rTree); return(num1+num2+1); int Twochild(Tree*tree)/度为2的 int n=0; if(tree=