アルゴリズム導論12.1-3

テーマ:実行中シーケンス遍歴の非再帰アルゴリズムを設計する
 
回答:
分析:
1.スタックを使用して再帰呼び出しのプロセスをシミュレートする.すなわち、中序遍歴を実現することができる
2、ノードにポインタドメインを追加し、そのポインタドメインが親ノードを指すようにし、反復によって中序遍歴を実現する
 
非再帰アルゴリズム:
スタックシミュレーションアルゴリズムバージョン1:

// 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になります.
 
スタックシミュレーションアルゴリズムバージョン2:

// 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)