2

Morris ツリー トラバーサルの実装を見つけました。

正常に動作しますが、逆の順序でツリーをトラバースしようとすると少し問題が発生します.. -

    void MorrisTraversal(struct Node *root)
    {  
    struct Node *p,*pre;
    if(root==0) { return; }
    for(p=root;p!=0;)
    {
    if(p->Left==0) { printf(" %d ",p->Data); p=p->Right; continue; }
    for(pre=p->Left;pre->Right!=0 && pre->Right!=p;pre=pre->Right) { }
    if(pre->Right==0)
        { pre->Right=p; p=p->Left; continue; }
    else
        { pre->Right=0; printf(" %d ",p->Data); p=p->Right; continue; }

    }
}
4

2 に答える 2

2

逆順とは、逆順トラバーサルを意味していると思います。少なくとも 2 つのオプションがあります。

  1. コードを変更して、すべての->Rightポインター参照を1 つに置き換えることができ->Leftます。

  2. printf2 つのステートメントをスタックへのプッシュに置き換えることができます。アルゴリズムが完了したら、スタックからデータを取り出して出力します。ただし、これは、スタックレスにする予定だったモリス トラバーサル アルゴリズムの目的全体を無効にします。

この関連するSO スレッドは、理解に役立つ場合があります。

これが役立つことを願っています。

于 2012-04-21T04:56:52.320 に答える