非递归遍历二叉树-蒲公英云

非递归遍历二叉树

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

经典算法：

递归时的函数调用，在非递归时即为参数压栈，递归时的调用函数返回，在非递归时即为栈顶元素出栈，在非递归中设遍历指针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代码段
            }
        }
    }
}

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

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

若压栈的顺序与遍历顺序相反，则出栈顺序即为遍历顺序，用压入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 );
        }
    }
}