莫里斯中序遍历

Question

从这里学习 morris 有序遍历：http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/ and Explain Morris inorder tree traversal without using stacks or recursion

我很困惑。评论里有3个问题。欢迎提供帮助。谢谢

    while (current != null) {
        if (current.left == null) {
            visit(current);
            current = current.right;
        } else {
            pre = current.left;
            while (pre.right != null && pre.right != current) {
                pre = pre.right;
            } // Q1: why "pre.right != current"?
              // pre is initialized as current.left and will go right until null, 
              // why compare pre.right with current?

            if (pre.right == null) {
                pre.right = current;
                current = current.left;
            } else { // Q2: In which case, pre.right is not null and program gets here?
                pre.right = null;// Q3: why set pre.right to null?
                visit(current);
                current = current.right;
            }   

        } 

    }

Answer 1

好的，如果我没理解错的话，这个遍历本质上是重构了树，使得最左边的节点位于树的根部。所以事情是这样开始的：

     D
   /   \
  B     F
 / \   / \
A   C E   G

看起来像这样：

A
 \
  B
 / \
A'  C
     \
      D
     / \
    B'  F
       / \
      E   G

其中 A' 是 A 及其所有子树。

访问后，它会重建树。

回答您的问题：

Q1

重建前，pre.right != current永远不会成为loop-ending条件，即永远不会为真。然而，在重建之后，想象一下如果 current 持有 B。 pre 将设置为 A'，与 A 相同。 pre.right == A'.right == A.right == current。因为这意味着 A' 节点已经被访问过，它打破循环并重建它，这导致你的下一个问题。

Q2

同样，这种情况在树的重建之前永远不会发生，但在重建之后，这是 "what to do" 当您到达一个已经访问过的节点时。这又引出了你的下一个问题。

Q3

pre.right 设置为 null 因为这意味着在重建之前，pre.right 最初是空的。查看案例post-reconstruction，节点B，pre设置为A，是叶节点，没有权限child。因此修复它：

  B
 / \
A   C
     \
      D
     / \
    B'  F
       / \
      E   G

如你所见，A' 变成了 A 因为它是正确的 child 不再是 B 而是 null。

本质上，为了帮助您更好地理解它：

Morris 遍历重建树使其根成为最左边的节点（另请注意，它现在具有循环路径）
重构后会访问，然后修复重构回原来的样子

莫里斯中序遍历

Morris inorder Traversal

algorithm

tree

binary-tree

graph-traversal