在不使用堆栈或递归的情况下解释Morris inorder树遍历

Question

有人可以帮我理解下面的Morris inorder树遍历算法而不使用堆栈或递归吗？我试图了解它是如何工作的,但它只是逃避了我.

 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和使用该财产序遍历.但除此之外,我迷失了.

编辑:找到这个附带的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有一个左边的孩子,因此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.树的其余部分遵循相同的模式.

不需要递归,因为不依赖于通过堆栈的回溯,而是返回到(子)树的根的链接被移动到在递归的inorder树遍历算法中将被访问的点 - 无论如何左子树已经完成了.

Answer 2

我在这里为算法制作了动画：https : //docs.google.com/presentation/d/11GWAeUN0ckP7yjHrQkIB0WT9ZUhDBSa-WR0VsPU38fg/edit?usp=sharing

这应该有助于理解。蓝色圆圈是光标，每张幻灯片都是外部 while 循环的迭代。

这是莫里斯遍历的代码（我从 geeks for geeks 复制并修改了它）：

def MorrisTraversal(root):
    # Set cursor to root of binary tree
    cursor = root
    while cursor is not None:
        if cursor.left is None:
            print(cursor.value)
            cursor = cursor.right
        else:
            # Find the inorder predecessor of cursor
            pre = cursor.left
            while True:
                if pre.right is None:
                    pre.right = cursor
                    cursor = cursor.left
                    break
                if pre.right is cursor:
                    pre.right = None
                    cursor = cursor.right
                    break
                pre = pre.right
#And now for some tests. Try "pip3 install binarytree" to get the needed package which will visually display random binary trees
import binarytree as b
for _ in range(10):
    print()
    print("Example #",_)
    tree=b.tree()
    print(tree)
    MorrisTraversal(tree)

Answer 3

递归中序遍历是：(in-order(left)->key->in-order(right))。（类似于DFS）

在执行DFS时，我们需要知道回溯到的位置（这就是我们通常保留堆栈的原因）。

当我们经过一个父节点时，我们需要回溯到->我们找到需要从中回溯的节点，并将其链接更新到父节点。

我们什么时候回溯？当我们无法走得更远时。什么时候我们不能走得更远？没有孩子的礼物时。

我们回溯到哪里？通知：致成功！

因此，当我们沿着左孩子路径跟随节点时，请在每个步骤中将前任节点设置为指向当前节点。这样，前任者将具有到后任者的链接（用于回溯的链接）。

我们会尽一切可能向左走，直到需要回溯为止。当我们需要回溯时，我们将打印当前节点，并按照正确的链接指向后继节点。

如果我们刚刚回溯->我们需要跟随合适的孩子（我们与左边的孩子在一起）。

如何判断我们是否刚刚回溯？获取当前节点的前任节点，并检查它是否具有正确的链接（到此节点）。如果有-那么我们会遵循它。删除链接以还原树。

如果没有左链接=>我们没有回溯，应该跟随左孩子。

这是我的Java代码（很抱歉，它不是C ++）

public static <T> List<T> traverse(Node<T> bstRoot) {
    Node<T> current = bstRoot;
    List<T> result = new ArrayList<>();
    Node<T> prev = null;
    while (current != null) {
        // 1. we backtracked here. follow the right link as we are done with left sub-tree (we do left, then right)
        if (weBacktrackedTo(current)) {
            assert prev != null;
            // 1.1 clean the backtracking link we created before
            prev.right = null;
            // 1.2 output this node's key (we backtrack from left -> we are finished with left sub-tree. we need to print this node and go to right sub-tree: inOrder(left)->key->inOrder(right)
            result.add(current.key);
            // 1.15 move to the right sub-tree (as we are done with left sub-tree).
            prev = current;
            current = current.right;
        }
        // 2. we are still tracking -> going deep in the left
        else {
            // 15. reached sink (the leftmost element in current subtree) and need to backtrack
            if (needToBacktrack(current)) {
                // 15.1 return the leftmost element as it's the current min
                result.add(current.key);
                // 15.2 backtrack:
                prev = current;
                current = current.right;
            }
            // 4. can go deeper -> go as deep as we can (this is like dfs!)
            else {
                // 4.1 set backtracking link for future use (this is one of parents)
                setBacktrackLinkTo(current);
                // 4.2 go deeper
                prev = current;
                current = current.left;
            }
        }
    }
    return result;
}

private static <T> void setBacktrackLinkTo(Node<T> current) {
    Node<T> predecessor = getPredecessor(current);
    if (predecessor == null) return;
    predecessor.right = current;
}

private static boolean needToBacktrack(Node current) {
    return current.left == null;
}

private static <T> boolean weBacktrackedTo(Node<T> current) {
    Node<T> predecessor = getPredecessor(current);
    if (predecessor == null) return false;
    return predecessor.right == current;
}

private static <T> Node<T> getPredecessor(Node<T> current) {
    // predecessor of current is the rightmost element in left sub-tree
    Node<T> result = current.left;
    if (result == null) return null;
    while(result.right != null
            // this check is for the case when we have already found the predecessor and set the successor of it to point to current (through right link)
            && result.right != current) {
        result = result.right;
    }
    return result;
}

Answer 4

我找到了一个非常好的莫里斯遍历的图片解释。