递归和非递归遍历二叉树

数据结构（双语）——项目文档报告递归、非递归两种算法遍历二叉树专业：计算机科学与技术班级：指导教师：苏亚光姓名：学号：第-2-页共16页目录一、设计思想……………………………………………………………….3页二、算法流程图……………………………………………………………4.页三、源代码…………………………………………………………………10页四、运行结果……………………………………………………………..15页五、遇到的问题及解决……………………………………………………15页六、心得体会………………………………………………………………16页第-3-页共16页一、设计思想1.递归遍历二叉树算法思想:1．先序遍历：首先判断根结点是否为空，为空则停止遍历，不为空则将左子作为新的根结点重新进行上述判断，左子遍历结束后，再将右子作为根结点判断，直至结束。到达每一个结点时，打印该结点数据，即得先序遍历结果。若二叉树非空，则依次进行如下操作：（1）访问跟结点；（2）前序遍历左子树；（3）前序遍历右子树。2.中序遍历：首先判断该结点是否为空，为空则结束，不为空则将左子作为根结点再进行判断，打印左子，然后打印二叉树的根结点，最后再将右子作为参数进行判断，打印右子，直至结束。若二叉树非空，则依次进行如下操作：（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。3.后续遍历：指针到达一个结点时，判断该结点是否为空，为空则停止遍历，不为空则将左子作为新的结点参数进行判断，打印左子。左子判断完成后，将右子作为结点参数传入判断，打印右子。左右子判断完成后打印根结点。若二叉树非空，则依次进行如下操作：（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。2.非递归遍历二叉树算法思想:1.先序遍历：建立一个栈，当指针到达根结点时，打印根结点，判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈，将左子作为新的根结点进行判断，方法同上。若当前结点没有左子，则直接将右子打印，同时将右子作为新的根结点判断。若当前结点没有右子，则打印左子，同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子，则当前结点为叶子结点，此时将从栈中出栈一个元素，作为当前的根结点，打印结点元素，同时将当前结点同样按上述方法判断，依次进行。直至当前结点的左右子都为空，且栈为空时，遍历结束。2.中序遍历：建立一个栈，当指针到达根结点时，把根结点压栈，判断根结点是否有左孩子。有左孩子的话将左孩子，将新结点入栈，然后再将指针指向当前结点的左子，直至左子为空，弹栈一个元素，作为当前结点，打印该栈顶元素，将指针指向当前结点右子，将右子作为新的结点，结点入栈，再次进行上面的判断，直至当前结点右子也为空，则再出栈一个元素作为当前结点，一直到结束，使得当前结点右子为空，且栈空，遍历结束。第-4-页共16页3.后续遍历：建立一个栈，然后定义一个tag，取值为0，1，0代表右子没有去过，1代表去过。①初始时指针指向根结点，将根结点压栈，指针指向左子，则将左子作为当前结点，继续判断直至左孩子为null，设q=null，tag=1。然后取得栈顶元素，设为当前结点，判断当前结点的右孩子是否等于q，如果相等，则打印当前结点，然后弹出当前结点，并且令q=当前结点的值。然后继续判断，直至右孩子不等于q，则将指针指向右孩子，把右孩子设为当前结点，令tag=0，继续步骤①，直到全部元素弹栈，栈为空时，遍历结束。二、算法流程图图1.先序递归流程图开始判断结点是否为空null访问根结点结束先序方式遍历左子树先序方式遍历右子树是否第-5-页共16页图2.中序递归流程图开始判断结点是否空按中序方式遍历左子树结束访问根结点按中根遍历方式遍历右子树YN第-6-页共16页图3.后序递归流程图开始判断结点是否空按后根遍历方式遍历左子树结束按后根遍历方式遍历右子树访问根结点YN第-7-页共16页图4.先序非递归流程图开始申请一个栈stack判断结点是否空输出结点值，压栈，指针指向它的左孩子判断结点是否空弹出栈顶元素，指向结点的右孩子结束判断栈或结点是否空NYNYN第-8-页共16页图1.流程图图2.流程图图3..流程图图5.中序非递归流程图开始申请一个stack判断结点是否空把结点压栈，指针指向它的左孩子判断结点是否空弹栈，设为当前结点，打印结点值，指向右孩子结束判断栈或结点是否空NYYNN第-9-页共16页图6.后序非递归流程图开始申请一个栈stack，用一个bool变量tag标记右孩子已被访问把当前结点压栈，p=p-lchildtop++判断标志tag是否为1输出结点值p=s.pop()p=p-rchild结束NYYNNYYN判断结点是否空判断栈或结点是否为空判断结点是否空第-10-页共16页三、源代码下面给出的是实现递归和非递归遍历二叉树的算法程序的源代码（合并在一起）：#includestdio.h#includestdlib.h#defineMAX100//定义堆栈最大容量enumBOOL{False,True};enumRVISIT{Rchildnovisit,Rchildvisit};//在后序遍历二叉树时用来指示是否已访问过右子树typedefstructBiTNode//定义二叉树节点结构{chardata;//数据域structBiTNode*lchild,*rchild;//左右孩子指针域}BiTNode,*BiTree;typedefstruct//定义堆栈结构{BiTreeelem[MAX];//栈区inttop;//栈顶指针}BiTreeStack;voidInitial(BiTreeStack&);//初始化一个堆栈BOOLPush(BiTreeStack&,BiTree);//将一个元素入栈BOOLPop(BiTreeStack&,BiTree&);//将一个元素出栈BOOLGettop(BiTreeStack,BiTree&);//取得堆栈栈顶元素BOOLStackEmpty(BiTreeStack);//判断堆栈是否已空voidCreateBiTree(BiTree&);//生成一个二叉树voidPreOrder(BiTree);//先序非递归遍历二叉树voidInOrder(BiTree);//中序非递归遍历二叉树voidPostOrder(BiTree);//后序非递归遍历二叉树voidPreTravel(BiTree);//先序递归遍历二叉树voidMidTravel(BiTree);//中序递归遍历二叉树voidPostTravel(BiTree);//后序递归遍历二叉树intmain(){BiTreeT;intflag=1;//标记BOOLtemp;printf(二叉树的递归和非递归遍历\n);CreateBiTree(T);//生成一棵二叉树printf(\n);第-11-页共16页printf(递归先序遍历二叉树:);PreTravel(T);printf(\n);printf(\n);printf(递归中序遍历二叉树:);MidTravel(T);printf(\n);printf(\n);printf(递归后序遍历二叉树:);PostTravel(T);printf(\n\n\n);if(T){printf(\n\n);printf(非递归先序遍历二叉树:);PreOrder(T);printf(\n);}elseprintf(二叉树为空\n);if(T){printf(非递归中序遍历二叉树:);InOrder(T);printf(\n);}elseprintf(二叉树为空\n);if(T){printf(非递归后序遍历二叉树:);PostOrder(T);printf(\n\n\n);}elseprintf(二叉树为空\n);}voidInitial(BiTreeStack&S){S.top=-1;//栈顶指针初始化为-1}BOOLPush(BiTreeStack&S,BiTreech){//将元素ch入栈，成功返回True,失败返回Falseif(S.top=MAX-1)returnFalse;//判断是否栈满else{S.top++;//栈顶指针top加一第-12-页共16页S.elem[S.top]=ch;//入栈returnTrue;}}BOOLPop(BiTreeStack&S,BiTree&ch){//将栈顶元素出栈,成功返回True，并用ch返回该元素值，失败返回Falseif(S.top=-1)returnFalse;//判断是否栈空else{S.top--;//栈顶指针减一ch=S.elem[S.top+1];returnTrue;}}BOOLGettop(BiTreeStackS,BiTree&ch){//取得栈顶元素，成功返回True，并用ch返回该元素值，失败返回Falseif(S.top=-1)returnFalse;else{ch=S.elem[S.top];//显示栈顶元素returnTrue;}}BOOLStackEmpty(BiTreeStackS){//判断堆栈是否已空，若空返回True,不空返回Falseif(S.top=-1)returnTrue;elsereturnFalse;}voidCreateBiTree(BiTree&T){//生成一棵二叉树，该二叉树以T为根结点charch;scanf(%c,&ch);//读入一个字符if(ch=='')T=NULL;else{T=(BiTNode*)malloc(sizeof(BiTNode));//生成一个新结点T-data=ch;CreateBiTree(T-lchild);//生成左子树CreateBiTree(T-rchild);//生成右子树}}voidPreTravel(BiTreeT){//先序遍历if(T){printf(%c,T-data);PreTravel(T-lchild);第-13-页共16页PreTravel(T-rchild);}}voidMidTravel(BiTreeT){//中序遍历if(T){MidTravel(T-lchild);printf(%c,T-data);MidTravel(T-rchild);}}voidPostTravel(BiTreeT){//后序遍历if(T){PostTravel(T-lchild);PostTravel(T-rchild);printf(%c,T-data);}}voidPreOrder(BiTreeT){//先序非递归遍历以T为根结点的二叉树BiTreeStackS;BiTreep;Initial(S);p=T;while(p||!StackEmpty(S)){if(p){printf(%c,p-data);Push(S,p);p=p-lchild;}else{Pop(S,p);p=p-rchild;}}printf(\n);}voidInOrder(BiTreeT){//中序非递归遍历以T为根结点的二叉树BiTreeStackS;第-14-页共16页BiTreep;Initial(S);p=T;while(p||!StackEmpty(S)){if(p){Push(S,p);p=p-lchild;}else{Pop(S,p);printf(%c,p-data);p=p-rchild;}}printf(\n);}voidPostOrder(BiTreeT){//后序非递归遍历以T为根结点的二叉树BiTreeStackS;BiTreep,q;RVISITtag;Initial(S);p=T;do{while(p){Push(S,p);p=p-lchild;}q=NULL;tag=Rchildvisit;while(!StackEmpty(S)&&tag){Gettop(S,p);if(p-rchild==q){pri