用递归-非递归两种方法遍历二叉树

用递归和非递归实现二叉树的遍历-1-一、设计思想递归实现二叉树遍历的思想:1.要遍历二叉树首先的问题是创建二叉树。二叉树的创建可以采用很多的方法。例如：先序，中序，后序，还可以采用层次的方法创建二叉树。本程序采用的是先序递归的方式创建的二叉树。2.然后是中序，先序，后序递归遍历二叉树。递归的思想是一直调用方法本身。3.中序递归遍历二叉树的思想是先访问左子树，然后访问根节点，最后访问右子树。当访问左子树或是右子树的时候，实际上调用的是函数本身。在这里就体现了递归的思想，当函数的返回值是0的时候，则返回上一次的程序，继续执行下面的语句。4.先序递归遍历二叉树的思想是先访问根节点，然后访问左子树，最后访问右子树。同样如步骤3的方式相同，当访问左子树或者是右子树的收，实际上调用的是函数本身，直到返回值是0的时候，返回上一层的程序继续执行。5.后序递归遍历二叉树的思想是先访问左子树，然后访问右子树，最后访问根节点。同样跟步骤3的方式相同，当访问左子树或者右子树的时候实际上是调用的是方法本直到有返回值的时候才返回上一层的程序，继续执行.非递归实现二叉树遍历的思想:1.跟递归遍历二叉树的前提一样，首先应该创建一个二叉树，同样使用先序递归的方式创建二叉树。2.然后是中序，先序，后序非递归遍历二叉树。3.中序非递归遍历二叉树的思想是：首先是根节点压栈，当根节点的左子树不是空的时候，左子树压栈。直到左子树为空的时候，不再压栈。将栈顶元素出栈，访问栈顶元素，并将栈顶的右子树进栈。当右子树的左子树不是空的时候，左子树一直进栈，直到左子树为空，则不再进栈。重复上面的操作，直到栈空的时候。4.先序非递归遍历二叉树的思想是：首先是根节点进栈，然后当栈不为空的时候，将栈顶元素出栈，然后访问。同时将出栈元素的右子树进栈，左子树进栈。重复上面的操作，直到栈为空。5.后序非递归遍历二叉树的思想：首先是根节点进栈，当根节点的左子树不为空的时候，左子树进栈，直到左为空的时候，左子树不再进栈。指针指向的是右子树，当右子树为空的时候，直接访问根节点。当右子树不为空的时候，则右子树的指针进栈，当右子树的左子树不为空的时候，则左也进栈，直到左为空。重复上面的操作，直到栈为空的时候，则遍历树完成。二、算法流程图递归方法遍历二叉树的流程图如图1用递归和非递归实现二叉树的遍历-2-图1递归方法遍历二叉树流程图非递归先序遍历二叉树流程图图2：非递归先序遍历二叉树流程图开始始创建二叉树树输入要遍历的二叉树树B!=NUll访问根节点点先序遍历(左子树)树)先序遍历(右子树)树)先序遍历历中序遍历历B!=NULL中序遍历(左子树)树)访问根节点点中序遍历(右子树)树)后序遍历历B!=NULL后序遍历(左子树)树)后序遍历(右子树)树)访问根节点点结束束结束束结束束YNNYYN开始输入遍历的二叉树创建二叉树根节点进栈栈不空出栈左进栈右进栈访问根Y结束N开始输入遍历的二叉树创建二叉树根节点进栈栈不空出栈左进栈右进栈访问根Y结束N用递归和非递归实现二叉树的遍历-3-后序非递归遍历二叉树流程图如图3图3后序非递归遍历二叉树流程图开始指针P指向根节点*q=pp!=NULLYP的左孩子不为空Y将P入栈并使p=p-leftChild输出p-data,并使q=pNP不为空且（P的右孩子为空或p-rightChild==q)Y栈是否为空N结束p=S.top()并弹出栈顶元素YN将P入栈并使p=p-rightChildN输入要遍历的二叉树创建二叉树用递归和非递归实现二叉树的遍历-4-中序非递归遍历二叉树流程图4图4：中序非递归遍历二叉树流程三、源代码用递归的方式实现二叉树的遍历#includestdio.h#includeconio.h#includestdlib.h/*定义二叉树*/typedefstructnode{chardata;structnode*lchild,*rchild;}BinTnode;开始输入遍历的二叉树创建二叉树根节点进栈栈不空左进栈取栈顶并不为空Y出栈栈不空出栈N右进栈N结束访问栈顶Y用递归和非递归实现二叉树的遍历-5-typedefBinTnode*BinTree;//定义二叉树类型的指针/*先序创建二叉树*/intCreateBinTree(BinTree*T){/*BinTree本身是一种类型，是一个指针，是指向结果体指针的类型*///这算是问题一//问题二是：关于栈的各种各样的操作，进栈，进的应该是指向树根的指针//问题三是：为什么要定义一个指向指针的指针？？？？？？？？？？？？charch;*T=(BinTree)malloc(sizeof(BinTnode));if(!*T)printf(overflow);do{ch=getchar();if(ch==''){*T=NULL;return0;}else{(*T)-data=ch;CreateBinTree(&((*T)-lchild));CreateBinTree(&((*T)-rchild));return1;}}while(ch!='\0');}/*中序递归遍历*/voidInorderTransverse(BinTrees){if(s){InorderTransverse(s-lchild);printf(%c,s-data);InorderTransverse(s-rchild);用递归和非递归实现二叉树的遍历-6-}}//先序递归遍历二叉树voidPreOrderTranverseTree(BinTrees){if(s){printf(%c,s-data);PreOrderTranverseTree(s-lchild);PreOrderTranverseTree(s-rchild);}}//后序递归遍历二叉树voidPostOrderTranverseTree(BinTrees){if(s){PreOrderTranverseTree(s-lchild);PreOrderTranverseTree(s-rchild);printf(%c,s-data);}}/*主方法*/voidmain(){BinTreeT;printf(请按照先序的顺序输入要创建的树:\n);CreateBinTree(&T);/*中序序列创建二叉树*/printf(中序递归遍历的序列是:);InorderTransverse(T);printf(\n);//先序递归遍历printf(先序递归遍历的序列是:);PreOrderTranverseTree(T);printf(\n);//后序递归遍历printf(后序递归遍历的序列是:);PostOrderTranverseTree(T);printf(\n);用递归和非递归实现二叉树的遍历-7-}用非递归的方式实现二叉树的遍历#includestdio.h#includeconio.h#includestdlib.h/*定义二叉树*/typedefstructnode{chardata;structnode*lchild,*rchild;}BinTnode;typedefBinTnode*BinTree;//定义二叉树类型的指针/*栈的相关操作*/typedefstruct{BinTreedata[100];inttop;}SeqStack;/*初始化栈*/voidinitStack(SeqStack*S){S-top=-1;}/*进栈*/voidPush(SeqStack*S,BinTreex){/*无论是进栈还是取栈顶元素都应该是指向树的指针*/if(S-top==100-1){printf(thestackisoverflow);}else{S-top=S-top+1;S-data[S-top]=x;}用递归和非递归实现二叉树的遍历-8-}/*出栈*/intPop(SeqStack*S,BinTree*p){if(S-top==-1){printf(thestackisunderflow);return0;}else{*p=S-data[S-top];--S-top;return1;}}/*判断栈是不是空*/intEmptyStack(SeqStackS){if(S.top==-1)return1;elsereturn0;/*栈不空的情况*/}/*取出栈顶元素*/intGetTop(SeqStackS,BinTree*p){//如果栈顶元素取到的是一颗子树的话，那应该返回的是。。。。，栈顶取到的到底应该是什么哈if(S.top==-1){printf(thestackisempty);return0;}else{*p=S.data[S.top];return1;}用递归和非递归实现二叉树的遍历-9-}//访问结点charvisit(BinTreep){return(*p).data;}/*创建二叉树*/intCreateBinTree(BinTree*T){/*BinTree本身是一种类型，是一个指针，是指向结果体指针的类型*///这算是问题一//问题二是：关于栈的各种各样的操作，进栈，进的应该是指向树根的指针//问题三是：为什么要定义一个指向指针的指针？？？？？？？？？？？？charch;*T=(BinTree)malloc(sizeof(BinTnode));if(!*T)printf(overflow);else{do{ch=getchar();if(ch!=’’)*T=NULL;return0;else{(*T)-data=ch;CreateBinTree(&((*T)-lchild));CreateBinTree(&((*T)-rchild));return1;}}while(ch!='\0');}}/*中序非递归遍历*/voidInorderTransverse(BinTreeT){SeqStackS;BinTreep;用递归和非递归实现二叉树的遍历-10-initStack(&S);//初始化栈printf(中序非递归序列是:);Push(&S,T);//根指针进栈T为指向二叉树的指针while(!EmptyStack(S)){//栈不是空的情况while(GetTop(S,&p)&&p)Push(&S,p-lchild);//gettop得到的结果也必须是一棵子树才行,进栈应该进的是树根的指针Pop(&S,&p);if(!EmptyStack(S)){//printf(%c,visit(p));Pop(&S,&p);printf(%c,visit(p));Push(&S,p-rchild);}}}/*先序非递归遍历*/voidPreorderTransverse(BinTreeT){SeqStackS;BinTreep;initStack(&S);//初始化栈Push(&S,T);//根指针进栈T为指向二叉树的指针printf(先序非递归序列是:);while(!EmptyStack(S)){Pop(&S,&p);//根节点出栈if(p!=NULL){printf(%c,visit(p));Push(&S,p-rchild);Push(&S,p-lchild);}}}/*后序非递归遍历*/用递归和非递归实现二叉树的遍历-11-voidPostorderTransverse(BinTreeT){SeqStackS;BinTreep,q;initStack(&S);//初始化栈p=T;printf(后序非递归序列是:);while(p||!EmptyStack(S)){//跳出while循环的原因是因为左子树或者右子树为空了if(p!=q){while(p!=NULL){Push(&S,p);if(p-lchild!=NULL)p=p-lchild;elsep=p-rchild;}}if(EmptyStack(S))break;GetTop(S,&q);if(q-rchil