非递归遍历二叉树

太过爱你忘了你带给我的痛 2023-10-06 13:33 35阅读 0赞

## 非递归遍历二叉树 ##

需按照递归遍历的思想，将递归算法转换为非递归算法

#### 经典算法： ####

递归时的函数调用，在非递归时即为参数压栈，递归时的调用函数返回，在非递归时即为栈顶元素出栈，在非递归中设遍历指针p，指向当前遍历的节点，在递归时即为指示当前递归调用函数的参数的指针

###### 中序遍历的访问过程： ######

###### 思路： ######

在递归遍历时，若递归函数为f，则执行顺序为f(left),root,f(right)  
转化为非递归：  
1.沿着根的左孩子，依次入栈，直到左孩子为空，说明已找到可以输出的节点  
2.栈顶元素出栈并访问，若该节点右孩子为空，则继续执行2（对应的递归遍历时的操作为当前递归调用返回后，上一层递归调用执行visit(root)操作）；若其右孩子不空，该节点的右子树执行1

###### 代码： ######

void Inorder(BiTree T)
    {
        
    	InitStack(S);
    	BiTree p=T;
    	while( p||!IsEmpty(S) )
    	{
        
    		if( p )
    		{
        
    			push( s,p );
    			p=p->lchild;
    		}
    		else
    		{
        
    			pop( s,p );
    			visit( p );
    			p=p->rchild;
    		}
    	}
    }

###### 先序遍历的访问过程： ######

###### 思路： ######

在递归遍历时，先序遍历的执行顺序为root,f(left),f(right)  
同理可转换为非递归

void Preorder( BiTree T )
    {
        
    	InitStack( s );
    	BiTree p=T;
    	while( p||!IsEmpty( s ) )
    	{
        
    		if( p )
    		{
        
    			push( s,p );
    			visit( p );
    			p=p->lchild;
    		}
    		else
    		{
        
    			pop( s,p );
    			p=p->rchild;
    		}
    	}
    }

###### 后序遍历时的访问过程： ######

###### 思路： ######

在递归遍历时，执行顺序为f(left),f(right)，root  
转化为非递归：  
1.沿着根的左孩子，依次入栈，直到左孩子为空  
2.读栈顶元素，若其右孩子不空且未被访问过，将右子树转而执行1；否则，栈顶元素出栈并访问，之后将遍历指针p退回到当前栈顶，继续执行2

为何要加上“未被访问过”这一限制条件，因为当其右子树遍历完，其右孩子退栈时，遍历指针又重新指向该节点，若不加限制条件，又会重新遍历其右子树；若右子树已被访问过，则表明左右子树均已遍历，该节点可直接退栈。

或者从递归遍历角度进行分析，需知道上一次的递归调用是从f(left)还是f(right)返回的，若从f(left)返回，则还需遍历根的右子树，若从f(right)返回，则直接可以访问根节点了，在非递归算法中对应的是右子树是否被访问过，被访问过即已经遍历完右子树，未被访问则已经遍历完左子树，还需遍历右子树。

设立指针r记录最近访问过的节点

###### 代码： ######

void Postorder( BiTree T )
    {
        
    	InitStack( s );
    	BiTree p=T;
    	BiTree r=NULL;
    	while( p || !IsEmpty(s) )
    	{
        
    		if( p )
    		{
        
    			push( s,p );
    			p=p->lchild;
    		}
    		else
    		{
        
    			GetTop( s,p );
    			if( p->rchild && p->rchild!=r )
    			{
        
    				p=p->rchild;
    				push( s,p );
    				p=p->lchild;
    			}
    			else
    			{
        
    				pop( s,p );
    				visit( p );
    				r=p;			//记录最近访问的节点
    				p=NULL;			//使得在下一次while循环中进入else代码段
    			}
    		}
    	}
    }

#### 统一形式的遍历算法（三种遍历形式统一）： ####

参考于[完全模仿递归，不变一行。秒杀全场，一劳永逸][Link 1]

若压栈的顺序与遍历顺序相反，则出栈顺序即为遍历顺序，用压入NULL指针指示可访问根节点，同时它也可以表示一次递归调用过程的返回（如中序遍历的NULL指针指示左子树遍历完成，后序遍历的NULL指针指示右子树遍历完成）

###### 先序： ######

###### 思路： ######

先序遍历顺序为根左右，则压入栈的顺序为右左根时，退栈顺序即为遍历顺序  
在右左根依次压入栈后，再向栈中压入NULL指针，表明下一次操作为弹出并访问根节点，弹出根节点后，接着对左右子树进行同样操作

void Preorder( BiTree T )
    {
        
    	InitStack( s );
    	BiTree p;
    	if( T!=NULL )
    		push( s,T );
    	while( !IsEmpty( s ) )
    	{
        
    		pop( s,p );
    		if( p!=NULL )
    		{
        
    			if( p->right ) 
    				push( s,p->right );
    			if( p->left )
    				push( s,p->left );
    			push( s,p );
    			push( s,NULL );
    		}
    		else
    		{
        
    			pop( s,p );
    			visit( p );
    		}
    	}
    }

###### 中序： ######

同理，入栈顺序为右根左，根入栈后再压入NULL指针，当NULL指针弹出时表明下一操作为访问根节点

void Preorder( BiTree T )
    {
        
    	InitStack( s );
    	BiTree p;
    	if( T!=NULL )
    		push( s,T );
    	while( !IsEmpty( s ) )
    	{
        
    		pop( s,p );
    		if( p!=NULL )
    		{
        
    			if( p->right ) 
    				push( s,p->right );
    			push( s,p );
    			push( s,NULL );
    			if( p->left )
    				push( s,p->left );
    		}
    		else
    		{
        
    			pop( s,p );
    			visit( p );
    		}
    	}
    }

###### 后序： ######

入栈顺序根右左

void Preorder( BiTree T )
    {
        
    	InitStack( s );
    	BiTree p;
    	if( T!=NULL )
    		push( s,T );
    	while( !IsEmpty( s ) )
    	{
        
    		pop( s,p );
    		if( p!=NULL )
    		{
        	
    			push( s,p );
    			push( s,NULL );
    			if( p->right ) 
    				push( s,p->right );
    			if( p->left )
    				push( s,p->left );
    		}
    		else
    		{
        
    			pop( s,p );
    			visit( p );
    		}
    	}
    }

[Link 1]: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/mo-fang-di-gui-zhi-bian-yi-xing-by-sonp/