c++ - 在不使用堆栈或递归的情况下解释 Morris 中序树遍历

Question

有人可以帮我理解以下不使用堆栈或递归的莫里斯中序树遍历算法吗？我试图了解它是如何工作的，但它只是逃避了我。

 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 节点 成为 中 max 节点 的 右子节点 >右子树并使用此属性进行中序遍历。但除此之外，我迷路了。

编辑: 找到了这个随附的 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 */
}

Answer 1

如果我没看错算法，这应该是它工作原理的一个例子:

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

首先，X是根，所以初始化为current。 X 有一个左 child ，因此 X 成为 X 左子树的最右 child —— 的直接前身X 在中序遍历中。所以 X 是 B 的右 child ，然后 current 被设置为 Y。树现在看起来像这样:

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

上面的

(Y) 指的是 Y 及其所有子代，由于递归问题而被省略。无论如何，重要的部分都列出来了。 现在树有一个指向 X 的链接，遍历继续……

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

然后输出A，因为没有左 child ，返回current给Y，变成A 在上一次迭代中的右 child 。在下一次迭代中，Y 有两个 child 。然而，循环的双重条件使它在到达自身时停止，这表明它的左子树已经被遍历。因此，它打印自己，并继续其右子树，即 B。

B打印自己，然后current变成X，和Y经历同样的检查过程做了，也意识到它的左子树已经被遍历，继续Z。树的其余部分遵循相同的模式。

不需要递归，因为不是依赖于通过堆栈回溯，而是将返回(子)树根的链接移动到递归中序树遍历算法中将访问它的点 - - 在它的左子树完成之后。