algorithm - 莫里斯中序遍历

Question

从这里学习莫里斯顺序遍历:http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/和 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 及其所有子树。

访问后，它会重建树。

回答您的问题:

第一季度

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

第二季度

同样，这种情况在树的重建之前永远不会发生，但在重建之后，这是当您到达一个已经访问过的节点时“应该做什么”。这又引出了您的下一个问题。

第三季度

pre.right 设置为 null 因为这意味着在重构之前，pre.right 原本是 null。查看重构后的案例，节点B，pre设置为A，是叶节点，没有右 child 。从而修复它:

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

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

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

• Morris 遍历重建树，使其根位于最左边的节点(另请注意，它现在具有循环路径)
• 一旦重构完成，它就会访问，然后将重构修复回原来的形式。