详解二叉树的递归遍历与非递归遍历——（二）

骑猪看日落 2021-11-10 23:06 528阅读 0赞

## 非递归遍历 ##

上一边文章中，咱们谈到了二叉树的递归遍历，也是十分的简单哈，这回又继续将非递归遍历写一下。从前序开始扯吧，哈哈！！！  
先给出存储结构：

> typedef struct Node\{  
> int data; //保存节点中的值  
> struct BTNode \*lchild; //左孩子指针  
> struct BTNode \*rchild; //右孩子指针  
> \}BTNode,\*BiTree;

#### 1.前序遍历 ####

*  先访问根结点；
 *  然后在访问左子树；
 *  最后访问右子树；

前序遍历大体流程：

1.  首先，扫描并访问根结点1，（这里用到一个保存节点的栈）然后将根结点保存到栈中，并将根节点指向他的左孩子2（如果存在）；
2.  然后开始循环，每一次循环都访问改结点，然后将该结点压入栈中，一直循环到某一时刻的左孩子为NULL的 时候，也就是访问到了A结点的左子树中的最深层左孩子7；
3.  则进行下一步，将结点指针指向该7的右孩子（如果存在），先访问该结点，然后继续访问该右孩子的左子树，重复第一步，就会一直自底向上的将1结点的左子树访问完毕；
4.  最后，当回到1结点时，根结点1和他的左子树已经全部遍历完成，则开始遍历右子树了。流程和第3步类似。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70 1]  
代码重现：

void  PreOrder(BiTree  T){
    	InitStack(S);	//初始化栈
    	BiTree p = T;	//将P指向T，作为遍历指针
    	while(p || !StackEmpty(S)){//p不为空或者栈不为空时候，继续遍历
    		if(p){
    			visit(p);	//访问根结点
    			Push(S,p);	//将根节点压入栈中
    			p = p->lchild; //往左子树走
    		}//if
    		//p为空跳到else表示已经访问到了左子树的最底层的那个左孩子；
            //现在要做的是从下往上一次打印左右节点（实际上只有右节点了）；
    		else{
    			Pop(S,p);//弹出栈顶元素，访问
    			p = p->rchild; //往右子树走
    		}
    	}//while
    }//PreOrder

可以说从整个流程比较简单。

#### 2.中序遍历 ####

中序遍历可以说是三种非递归遍历最简单的一种的。

*  先访问左子树；
 *  然后在访问根结点；
 *  最后访问右子树；

中序遍历大体流程：  
1. 先扫描根结点（并非访问根结点）的所有的左结点，并将它们一一入栈，直到扫描到最深层的左结点，即停止该操作。进而将栈顶元素弹出，这里设为\*p,（显然 \*p没有左孩子结点或左孩子结点均已经被访问郭），访问它。然后扫描该结点的右孩子结点，将其进栈，在扫描该右孩子的所有结点并一一进栈，如此继续，直到栈为空位置。

void InOrder(BiTree T){
    	InitStack(S);	//初始化栈
    	BiTree p = T;	//p作为遍历指针
    	while(p || !EmptStack(S)){     //只要p不为空，且栈不为空，就继续扫描
    		if(p){	//每次遇到非空二叉树，就向左走
    			push(S,p);
    			p=p->lchild;	
    		}else{	//跟指针退栈，访问根结点，遍历右子树
    			Pop(S,p);	//退栈
    			visit(p);	//访问根结点
    			p=p->rchild;	//在向右子树走
    		}
    	}	
    }

#### 3.后序遍历 ####

都说后续非递归是最难的。可是换个角度想想：你把最难的都掌握了，你就肯定不会比别人差，可能写的不好，但是请看下去。  
直接谈后序遍历的思想吧！  
————后序遍历就是先访问左子树，在访问右子树，最后访问根结点，当用堆栈来存储结点时，应该分清返回根节点时是从左子树访问返回的还是从右子树返回的，  
①因为如果是访问了左子树返回的，那么久还需要去访问右子树；  
②如果是从右子树返回的，则可以直接访问根结点了，这一点需要特别注意。  
所以这里借助辅助指针 preNode,指向醉经访问过的结点。也可在结点中增加一个标志域，记录是否已被访问。

void PostOrder(BiTree T){
    	InitStack(S);
    	p=T;
    	preNode=NULL;
    	while(p && !EmptyStack(S)){
    		if(p){	//走到最左边的结点
    			push(S,p);
    			p = p->lchild;
    		}else{	//向右
    			GetTop(S,p);	//去栈顶节点
    			if(p->rchild && p->rchild != preNode){
    				//若右子树存在，且未被访问过
    				p = p->rchild;	//转向右子树
    				push(S,p);		//压入栈
    				
    				p = p->lchild;	//再走到最左	
    			}//if
    			else{//否则，直接访问根结点了
    				pop(S,p);	//将该结点弹出
    				visit(p);	//访问改结点
    				preNode = p;	//记录最近访问过的结点
    				p = NULL;	//结点访问完后，重置指针p
    			}//else
    		}//else向右结尾
    	}//while
    }//PostOrder

**总的来说，二叉树的非递归遍历相对递归遍历是难理解一点的，但是非递归遍历算法的执行效率是要高于递归算法的。**

可能我有的地方说的不够详细、易懂，如果还是不大好理解；大家可以留言，我会尽我所能的去解释，或者是可以自己模拟一下，画一个二叉树，然后对着代码进行模拟一下流程，相信会很容易理解的。

希望大家无论遇到什么算法，都要静下心来，去想，去实践，去搜索，只有这样，才有提高。一起加油！！！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70]: /images/20211109/452089bb65d44cdbae53b1407f3046f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70 1]: /images/20211109/0cf3b247c7a0438784eb5e2f630d331e.png