解释Morris在顺序树遍历而不使用堆栈或递归 [英] Explain Morris inorder tree traversal without using stacks or recursion

问题描述

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

Can someone please help me understand the following Morris inorder tree traversal algorithm without using stacks or recursion ? I was trying to understand how it works, but its just escaping me.

 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

以当前节点的方式使 max节点的右子 / code>在右子树中，并使用此属性进行遍历。但除此之外，我迷路了。

I understand the tree is modified in a way that the current node, is made the right child of the max node in right subtree and use this property for inorder traversal. But beyond that, I'm lost.

编辑：
找到这个附带的c ++代码。我很难理解在修改后树是如何恢复的。魔术在于 else 子句，一旦右叶被修改，它就被命中。查看代码详细信息：

Found this accompanying c++ code. I was having a hard time to understand how the tree is restored after it is modified. The magic lies in else clause, which is hit once the right leaf is modified. See code for details:

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

推荐答案

正在读取算法，这应该是一个如何工作的例子：

If I am reading the algorithm right, this should be an example of how it works:

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

code> X 是根，所以它被初始化为 current 。 X 有一个左孩子，因此 X 是 X 的左子树 - 在顺序遍历中 X 的直接前导。所以 X 是 B 的正确子项，然后当前设置为 Y 。该树现在看起来像这样：

First, X is the root, so it is initialized as current. X has a left child, so X is made the rightmost right child of X's left subtree -- the immediate predecessor to X in an inorder traversal. So X is made the right child of B, then current is set to Y. The tree now looks like this:

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

上面的

<$> （Y）指的是 Y 对于递归问题省略。重要的部分被列出。
现在树有一个链接回X，遍历继续...

(Y) above refers to Y and all of its children, which are omitted for recursion issues. The important part is listed anyway. Now that the tree has a link back to X, the traversal continues...

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

然后 A 被输出，因为它没有左孩子，并且当前被返回到 Y A 是上一次迭代中的右子节点。在下一次迭代时，Y有两个孩子。然而，循环的双重条件使其在到达自身时停止，这表明它的左子树已经被遍历。所以，它打印自己，并继续它的右子树， B 。

Then A is outputted, because it has no left child, and current is returned to Y, which was made A's right child in the previous iteration. On the next iteration, Y has both children. However, the dual-condition of the loop makes it stop when it reaches itself, which is an indication that it's left subtree has already been traversed. So, it prints itself, and continues with its right subtree, which is B.

B 打印本身，然后当前变为 X 进程作为 Y ，也意识到它的左子树已经遍历，继续 Z 。

B prints itself, and then current becomes X, which goes through the same checking process as Y did, also realizing that its left subtree has been traversed, continuing with the Z. The rest of the tree follows the same pattern.

没有递归是必要的，因为它不是依赖于通过堆栈的回溯，而是链接回（sub）的根）树被移动到在递归的有序树遍历算法中被访问的点 - 在它的左子树完成之后。

No recursion is necessary, because instead of relying on backtracking through a stack, a link back to the root of the (sub)tree is moved to the point at which it would be accessed in a recursive inorder tree traversal algorithm anyway -- after its left subtree has finished.

这篇关于解释Morris在顺序树遍历而不使用堆栈或递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！