[解決済み] スタックや再帰を使わないMorrisの順次木探索について説明する。

質問

スタックや再帰を使用しない、以下のMorris inorder tree traversal アルゴリズムの理解を助けてくれる人はいますか？私はそれがどのように動作するかを理解しようとしたが、それはちょうど私をエスケープされています。

 1. Initialize current as root
 2. While current is not NULL
  If current does not have left child     
   a. Print current’s data
   b. Go to the right, i.e., current = current->right
  Else
   a. In current's left subtree, make current the right child of the rightmost node
   b. Go to this left child, i.e., current = current->left

という形でツリーが修正されるそうですね。 current node にすることで right child の max node で right subtree で、このプロパティを順次走査に使用します。しかし、その先には迷いがあります。

EDIT こんな付属のc++のコードを発見。ツリーを修正した後、どのように復元するのか理解するのに苦労しました。このマジックは else 節があり、これは右の葉が変更されるとヒットする。詳しくはコードをご覧ください。

/* Function to traverse binary tree without recursion and
   without stack */
void MorrisTraversal(struct tNode *root)
{
  struct tNode *current,*pre;

  if(root == NULL)
     return; 

  current = root;
  while(current != NULL)
  {
    if(current->left == NULL)
    {
      printf(" %d ", current->data);
      current = current->right;
    }
    else
    {
      /* Find the inorder predecessor of current */
      pre = current->left;
      while(pre->right != NULL && pre->right != current)
        pre = pre->right;

      /* Make current as right child of its inorder predecessor */
      if(pre->right == NULL)
      {
        pre->right = current;
        current = current->left;
      }

     // MAGIC OF RESTORING the Tree happens here: 
      /* Revert the changes made in if part to restore the original
        tree i.e., fix the right child of predecssor */
      else
      {
        pre->right = NULL;
        printf(" %d ",current->data);
        current = current->right;
      } /* End of if condition pre->right == NULL */
    } /* End of if condition current->left == NULL*/
  } /* End of while */
}

解決方法は？

もし私がこのアルゴリズムを正しく読んでいるならば、これがその動作の例となるはずです。

     X
   /   \
  Y     Z
 / \   / \
A   B C   D

最初に X はルートなので、初期化されます。 current . X は左の子を持っているので X の右端の右子として作成されます。 X の左サブツリーの直前である。 X を、順を追って探索する。そのため X の右の子として作成されます。 B であれば current が設定されます。 Y . これで、ツリーは次のようになります。

    Y
   / \
  A   B
       \
        X
       / \
     (Y)  Z
         / \
        C   D

(Y) 上記は Y とその子供たち全てです。再帰の問題で省略されています。重要な部分はとにかくリストアップする。 さて、このツリーにはXへのリンクがあるので、探索を続ける...。

 A
  \
   Y
  / \
(A)  B
      \
       X
      / \
    (Y)  Z
        / \
       C   D

次に A が出力されるのは、左の子がいないからであり current が返され Y されたものである。 A の右の子である。次の反復では、Yは両方の子を持つ。しかし、ループの二重条件により、ループは自分自身に到達すると停止する。これは、自分自身の左部分木がすでに走査されたことを示している。そこで、ループは自分自身を表示し、右の部分木である B .

B は自分自身を印刷し、その後 current になります。 X と同じチェックプロセスを経ます。 Y は、その左側のサブツリーがトラバースされたことも認識し、続けて Z . 残りのツリーも同じパターンになります。

再帰は必要ない。なぜなら、スタックをバックトラックする代わりに、（サブ）ツリーのルートへのリンクは、再帰的な木探索アルゴリズムでアクセスされるであろうポイント、つまり左サブツリーが終了した後に移動されるからである。