Morris traversalをポストオーダーに使用できますか？

Question

私は多くのウェブサイトにアクセスしましたが、MorrisのpostOrderトラバーサルのアルゴリズムは見つかりませんでした。 私は、preOrderとinOrderのためにMorrisアルゴリズムを使用できることを知っています。もし誰かがpostOrder Morrisアルゴリズムを教えてくれれば、大きな助けになるでしょう。

Answer 1

私はMorrisメソッドを使用してポストオーダートラバーサルを達成する方法を説明しようとします。 前提条件： 説明の前に、トラバーサルのポストオーダーは、順序通りのトラバーサルを修正することができます。

In-orderトラバーサルの場合、ルートノード から開始します。1.現在のノードが子を残している場合は、その先行ノードを見つけてルートの右の子としてルートの左に移動します。 [前の部分を見つけるために、その左のサブツリーに最大の要素を見つける] 2.現在のノードが子要素を残していない場合は、データを印刷して右に移動します。

復元ツリー：ステップ1を実行している間は、先行する右の子が現在のノードである点に到達します。これは、左の子全体がオフになり、データの印刷が開始されたときにのみ発生しますそこから。 [現在のノードの左の子が見つからなかった場合] この場合、右の子をそのノードから切り離す必要があります。

void MorriesInorder(BTnode root) { 
if(root == null) return; 
BTnode temp; 
while (root!=null){ 
    //case 2: when left child does not exist 
     if (root.left == null) { 
       print(root.data); 
       root = root.right; 
    }else { 
      //find predecessor 
      temp = root.left; 
      while (temp.right!=null && 
         temp.right!=root) // to check restore case 
        temp = temp.right; 

      if (temp.right == null) //predecessor found, converting 
      { 
         temp.right = root; 
         root = root.left; 
      } else { 
        print root.data; 
        temp.right = null; // cut right child off 
        root = root.right; 
      } 
    } 

}} 

元の質問に戻ると、ポストオーダートラバーサルをどのように実行しますか？ ポストオーダートラバーサルを達成するために、上記の概念を少し変更して使用します。 まず、ダミーノードを持ち、ツリー全体をダミーノードの左の子として作成し、右の子を空にします。 [ なぜ？私たちは、ルートの右の子がないと仮定して、左の子をプリニングし、ルートがポストオーダーのトラバーサルになると仮定すると、右]）] 次に何ですか？完了しましたか、いいえ... 新しいツリーでインオーダを実行するだけで意味がありません。元のツリーの後にダミーノードが続いていても、インオーダートラバーサルが印刷されます。 [INORDERトラバーサルで議論】ケース2

重要な部分から

まず削除印刷データ：今密接内側elseブロックを観察し、この注意を必要とするコードの一部。この一時的に拡張されたツリーは、インサイドelse節では、一時的な親を見つけた後、p.left（インクルード）とp（除外）の間のノードが、ツリーは逆の順序で処理されます。それらを一定の時間内に処理するために、ノードの連鎖はスキャンされ、右の参照はノードの親を参照するために逆転される。次に、同じチェーンが上にスキャンされ、各ノードが訪問され、正しい参照が元の設定に復元されます。

//This is Post Order :children before node(L ,R , N) 
void morrisPostorderTraversal(Node *root){ 

// Making our tree left subtree of a dummy Node 
Node *dummyRoot = new Node(0); 
dummyRoot->left = root; 

//Think of P as the current node 
Node *p = dummyRoot, *pred, *first, *middle, *last; 
while(p!=NULL){   

    if(p->left == NULL){ 
     p = p->right; 
    } else{ 
     /* p has a left child => it also has a predeccessor 
      make p as right child predeccessor of p  
     */ 
     pred = p->left; 
     while(pred->right!=NULL && pred->right != p){ 
      pred = pred->right; 
     } 

     if(pred->right == NULL){ 

      // predeccessor found for first time 
      // modify the tree 

      pred->right = p;  
      p = p->left; 

     }else {       

      // predeccessor found second time 
      // reverse the right references in chain from pred to p 
      first = p; 
      middle = p->left;    
      while(middle!=p){    
       last = middle->right; 
       middle->right = first; 
       first = middle; 
       middle = last; 
      } 

      // visit the nodes from pred to p 
      // again reverse the right references from pred to p  
      first = p; 
      middle = pred; 
      while(middle!=p){ 

       cout<<" "<<middle->data; 
       last = middle->right;   
       middle->right = first; 
       first = middle; 
       middle = last; 
      } 

      // remove the pred to node reference to restore the tree structure 
      pred->right = NULL;  
      p = p-> right; 
     } 
    } 
}  
}