递归非递归两种算法遍历二叉树

用递归、非递归两种方法遍历二叉树-1-一、设计思想1.用递归算法遍历设计思想：主要是通过不同程序顺序，从而实现递归的顺序遍历前序遍历：先判断节点是否为空，如果不为空，则输出。再判断左节点是否为空，如果不为空，则递归调用，直到遍历到最左边。接着再遍历最左边的右子树，如果此时右子树不为空，则递归遍历左子树的操作，直到遍历到叶子节点。如果右子树为空，则回溯上次的递归调用，重复输出和遍历右子树的操作。中序遍历：先遍历左节点是否为空，如果不为空，则递归调用，直到遍历到最左边或者叶子节点，然后输出，接着再遍历最左边的右子树，如果此时右子树不为空，则递归重复遍历左子树的操作，直到遍历到叶子节点。如果右子树为空，则回溯到上次递归调用，重复输出和遍历右子树的操作。后序遍历：先判断左节点是否为空，如果不为空则一直递归直到遍历到最左边，然后遍历右节点，再接着遍历到左子树的最右边，直到遍历到叶子节点。此时输出，回溯到上次递归，继续执行后面的操作，重复，直到将整个树遍历完毕。2.用非递归算法遍历设计思想：主要是通过栈的存取，判空，从而实现树的遍历前序遍历：通过一个循环实现。先输出节点的数值，因为栈的特性，则需要先判断右子树是否为空，如果不为空，则将右子树压栈。然后判断左子树是否为空，如果不为空，则将左子树压栈。接着再将栈里面的子树弹出赋给给当前节点变量，重复上述操作，直到栈为空后退出循环。中序遍历：通过循环实现。将树一直遍历到最左端，并将中间所经过的节点保存在栈中，当遍历到最左边的时候，则弹出栈里面的子树。输出数值，将当前节点赋值为当前节点的右子树，遍历右子树，即重复上述操作，直到当前节点为空，并且栈内元素为0。后序遍历：通过循环和标记栈实现。将数一直遍历到最左端，并将中间的节点保存在树栈中，同时同步的添加一个标记栈。当遍历到最左边的时候，弹栈并赋值给当前栈，然后判断标记栈的数值，如果数值为0的话则代表当前树没有遍历过，遍历右子树。然后重复上面的操作，如果数值为1的话则代表此时数已经遍历过了，可以开始输出了，为了避免重复输出，将当前栈赋为空。重复循环操作，直到栈内没有元素，且当前节点为空（因为一直左的操作并没有将右子树压栈）。用递归、非递归两种方法遍历二叉树-2-二、算法流程图图1递归算法-先序遍历图2递归算法-后序遍历图3递归算法-中序遍历开始Root=nullYN输出数据Root.getLTree=nullRoot=TreetRoot.getRTree=nullNYYN结束开始Root=TreetRoot=nullRoot.getLTree=nullNN输出数据YRoot.getRTree=null结束YN开始Root=TreetRoot=nullRoot.getLTree=nullRoot.getRTree=nullY输出数据结束YYYNNN用递归、非递归两种方法遍历二叉树-3-图4非递归算法-先序遍历图5非递归算法-中序遍历开始t.getRtree=nullTreet=rootoutputt=nullNYPusht.getLtree=nullPushNYN栈为空t=stack.pop()YN结束Y开始Treet=root压栈t=nullNYt=current.getLtree()t=stack.Pop()outputt=current.getRltree()栈为空N结束Y用递归、非递归两种方法遍历二叉树-4-图6非递归算法-后序遍历开始Treet=rootPusht=nullNYt=t.getLtree()标签栈压栈t=stack.pop()标签栈出栈赋值给标志位判断栈是否已经入栈过NYt=t.getRTree()标签栈压栈出栈并赋值tOutputCurrent=null树栈为空且当前节点为空N结束Y用递归、非递归两种方法遍历二叉树-5-三、源代码#includestdio.h#includestdlib.htypedefcharElemType;//定义树结构typedefstructtree{ElemTypedata;structtree*lchild;structtree*rchild;unsignedintisOut;//专为后序遍历设置的，0为不需要被输出，1为需要被输出}TreeNode,*Tree;//定义栈结构typedefstructstack{Tree*base;Tree*top;intstacksize;}SqStack;voidInitStack(SqStack&s);voidPush(SqStack&s,Treee);voidGetTop(SqStacks,Tree&e);voidPop(SqStack&s,Tree&e);intStackEmpty(SqStacks);voidCreateTree(Tree&t);voidPreOrder(Treet);voidPreOrder1(Treet);voidInOrder(Treet);voidInOrder1(Treet);voidPostOrder(Treet);voidPostOrder1(Treet);intmain(){TreeT;printf(\n按先序序列输入结点序列，'*'代表空：);CreateTree(T);printf(\n递归先序遍历的结果：);PreOrder(T);用递归、非递归两种方法遍历二叉树-6-printf(\n非递归先序遍历的结果：);PreOrder1(T);printf(\n递归中序遍历的结果：);InOrder(T);printf(\n非递归中序遍历的结果：);InOrder1(T);printf(\n递归后序遍历的结果：);PostOrder(T);printf(\n非递归后序遍历的结果：);PostOrder1(T);printf(\n);return0;}voidInitStack(SqStack&s)//初始化栈{s.base=(Tree*)malloc(100*sizeof(Tree));if(!s.base){printf(InitStack内存分配出错,程序将推出执行！\n);exit(-1);}s.top=s.base;s.stacksize=100;}voidPush(SqStack&s,Treee)//元素入栈接收一个stack类型变量和一个tree*类型变量{if(s.top-s.base=s.stacksize){s.base=(Tree*)realloc(s.base,(s.stacksize+20)*sizeof(Tree));if(!s.base){printf(Push内存分配出错,程序将退出执行\n);exit(-1);}s.top=s.base+s.stacksize;//s.stacksize+=20;}e-isOut=0;*s.top++=e;}voidGetTop(SqStacks,Tree&e)//获得栈顶元素用递归、非递归两种方法遍历二叉树-7-{e=*(s.top-1);//s.top为tree**类型}voidPop(SqStack&s,Tree&e)//出栈{if(s.top==s.base){printf(栈为空\n);return;}e=*(--s.top);}intStackEmpty(SqStacks)//判断栈是否为空{if(s.top==s.base)return1;return0;}voidCreateTree(Tree&t)//以先序序列建立树{charch;scanf(%c,&ch);if(ch=='*')t=NULL;else{t=(Tree)malloc(sizeof(TreeNode));if(!t){printf(分配内存出错！);return;}t-data=ch;CreateTree(t-lchild);CreateTree(t-rchild);}}voidPreOrder(Treet)//递归先序遍历，遍历顺序：根、左、右{用递归、非递归两种方法遍历二叉树-8-//先访问根节点，再先序遍历左子树，再先序遍历右子树if(t)//如果树t不为空树，才继续执行先序遍历{printf(%c,t-data);PreOrder(t-lchild);PreOrder(t-rchild);}}voidInOrder(Treet)//递归中序遍历，遍历顺序：左、中、右{//先中序遍历左子树，再访问根节点，再中序遍历右节点if(t)//如果树t为空树，则停止向下遍历{InOrder(t-lchild);printf(%c,t-data);InOrder(t-rchild);}}voidPostOrder(Treet)//递归后序遍历，遍历顺序：左、右、根{if(t){PostOrder(t-lchild);PostOrder(t-rchild);printf(%c,t-data);}}voidPreOrder1(Treet)//非递归先序遍历{Treep=t;//p为tree*类型变量SqStacks;InitStack(s);while(p||!StackEmpty(s))//当树的节点不为空或栈不为空执行循环{if(p)//当数的此节点不为空时，打印此节点值且将此节点入栈{printf(%c,p-data);Push(s,p);p=p-lchild;}用递归、非递归两种方法遍历二叉树-9-else//否则父节点出栈，p指向父节点的右子树{Pop(s,p);p=p-rchild;}}}voidInOrder1(Treet)//非递归中序遍历{Treep=t;SqStacks;InitStack(s);while(p||!StackEmpty(s)){if(p){Push(s,p);p=p-lchild;}else{Pop(s,p);printf(%c,p-data);p=p-rchild;}}}voidPostOrder1(Treet)//非递归后序遍历，遍历顺序：左、右、根{t-isOut=0;//初始值表示不输出Treep=t;SqStacks;InitStack(s);while(p||!StackEmpty(s))//节点非空或栈非空执行循环{if(p){if(p-isOut){//左右子树都已输出，则该节点也输出Pop(s,p);printf(%c,p-data);用递归、非递归两种方法遍历二叉树-10-if(!StackEmpty(s))GetTop(s,p);//得到该节点元素的父节点elsep=NULL;}else{if((p-lchild)&&(p-lchild-isOut==1)){//如果存在左子树,并且左子树已经遍历完，则说明该节点已经入栈p-isOut=1;p=p-rchild;}else//否则入栈该节点的树，并且走向它的左子树{Push(s,p);p=p-lchild;}}}else{GetTop(s,p);if(p-rchild){p=p-rchild;}else{Pop(s,p);printf(%c,p-data);p-isOut=1;if(!StackEmpty(s)){GetTop(s,p);if(p-lchild==NULL)p-isOut=1;//右子树已输出，将父节点isOut置1}elsep=NULL;}}}}用递归、非递归两种方法遍历二叉树-11-四、运行结果图7遍历二叉树运行结果图五、遇到的问题及解决这部分我主要遇到了如下三个问题，其内容与解决方法如下所列：第一个问题：递归的使用，没有完全理解递归的含义描述：递归的使用是每次都将上次调用的现场保留，直到本次的方法的完成才会返回上次的调用的现场，由于没有完全的了解，所以在调用的时候回忽略掉上次保存的现场。解决：通过例子来解决分析，每次将递归调用的现场都记录下来，然后再进行下次递归，从而避免了忽略掉的现场，得到错误的思想。第二个问题：非递归如何实现遍历描述：对于非递归，我