算法导论 12.1-3

题目:设计一个执行中序遍历的非递归算法

 

解答:

分析:

1、使用栈模拟递归调用的过程,即可以实现中序遍历

2、在结点中增加指针域,使该指针域指向父节点,通过迭代即可实现中序遍历

 

非递归算法:

栈模拟算法版本一:

// InOrder Traverasl
void InOrder( SearchTree T ) 
{
    Stack S;

    while( T != NULL || !S.Empty() )
    {
        if ( T != NULL )
        {
            S.push( T );
            T = T->Left; 
        }
        else
        {
            T = S.pop();
            Visit( T );
            T = T->Right;
        }
    }
}

注:该算法使用深度优先搜索技巧来实现,回溯时Visit。

 

栈模拟算法版本二:

// InOrder Traverasl version2.0
void InOrder( SearchTree T )
{
    Stack S;

    
    if( T != NULL )
        S.Push( T );
    
    T->ChildPushed = false;
    while ( !S.Empty() )
    {
        SearchTree TNode = S.Pop(); 
        if ( TNode->ChildPushed )
        {   
            // 如果标识位为true,则表示其左右子树都已经入栈,那么现在就需要访问该节点了
            Visit( TNode );        
        }
        else
        {   
            // 左右子树尚未入栈,则依次将 右节点,根节点,左节点 入栈
            if ( TNode->Right != NULL )
            {
                // 左右子树均设置为false
                TNode->Right->ChildPushed = false; 
                S.Push( TNode->Right );
            }
            TNode->ChildPushed = true;  // 根节点标志位为true
            S.Push( TNode );
            if ( TNode->Left != NULL )
            {
                TNode->Left->ChildPushed = false;
                S.Push( TNode->Left );
            }
        }
    }
}

注:该算法使用宽度优先搜索技巧,在通过标志ChildPushed标记是否可以Visit。

 

父节点实现版本:

void InOrder( SearchTree T )
{
    while ( T != NULL )
    {
        while ( T->Left != NULL && !T->Left->Visited )
            T = T->Left;

        if ( !T->Visited )
        {
            Visit( T );
            T->Visited = true;
        }

        if ( T->Right != NULL && !T->Right->Visited )
            T = T->Right;
        else
            T = T->Parent;
    }
}

注:使用该方法需要增加一个指向父节点的指针域,在建树时会存在一定困难

算法时间复杂度分析:O(N)

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。