Biri bana yığınları veya özyineleme kullanmadan aşağıdaki Morris O'na ağaç kastetmek algoritma anlamanıza yardım edebilir misiniz ? Nasıl çalışır, ama sadece benden uzak durmak onun anlamaya çalışıyordum.

 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

Ağaç 6**, right subtree max node right child yapılır ve O'na geçişi için bu özelliği kullanın bir şekilde değiştirilmiş olduğunu anlıyorum. Ama bunun ötesinde, ben kayboldum.

EDİT: Bulunan bu eşlik eden c kodu. Ağaç modifiye sonra geri nasıl anlamak zor bir zaman geçiriyordum. İşin sırrı, doğru yaprak değiştirilmiş bir zamanlar hit olan else yan yatıyor. Ayrıntılar için kod bakın:

/* 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 */
}

Eğer algoritma doğru okuyorum, bu nasıl bir örnek olmalıdır:

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

İlk, X kök current olarak başlatılır. X X Xen sağdaki sağ alt'O'na bir geçişi X ağacı -- hemen selefi s sol yapılmıştır. yani Sol bir çocuk var, X yapılmış B current sağ alt 22* *olarak ayarlanmıştır. Ağaç şimdi bu gibi görünüyor:

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

(Y) yukarıda Y özyineleme sorunları için atlanmış olan kendi çocuklarını, ifade eder. Önemli kısmı zaten listede. Ağacın bir bağlantısı X için geri şimdi, bu geçişi devam ediyor

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

A sol alt çünkü işitilir, ve current A yapılan Y, döndü'önceki yineleme haklı çocuk. sonra Sonraki yineleme, Y iki çocuk babasıdır. Ancak, döngünün çift durumu alt zaten geçiş olmuştur kalan bir göstergesi olduğunu kendisi ulaştığında durdurmak yapar. Bu yüzden, kendisini yazdırır, ve B hangi sağ alt ediyor.

B parmak izi kendisi ve sonra current olur X, geçer aynı kontrol süreci Y da farkında onun sol alt oldu geçilen, devam eden Z. Ağacın geri kalan kısmı da aynı yolu takip ediyor.

Hayır özyineleme gerekli, çünkü yerine güvenerek doğru ile bir yığın, bir bağlantı geri kök (alt)ağaç taşınır noktasında olan olur erişilen bir özyinelemeli O'na ağaç kastetmek algoritması her neyse ... sonra sol alt ağacı var bitmiş.