C++ 不使用堆栈或递归解释莫里斯中序树遍历

Explain Morris inorder tree traversal without using stacks or recursion

提问by brainydexter

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

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

我理解的树被修改的方式，将current node在作出right child的max node中right subtree和使用该财产序遍历。但除此之外，我迷路了。

EDIT: 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 elseclause, which is hit once the right leaf is modified. See code for details:

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

回答by Talonj

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

如果我正确阅读算法，这应该是它如何工作的一个例子：

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

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

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

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

(Y)above refers to Yand 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...

(Y)以上指的是Y及其所有子项，由于递归问题而省略了这些子项。无论如何都列出了重要的部分。现在树有一个回 X 的链接，遍历继续......

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

Then Ais outputted, because it has no left child, and currentis 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.

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

Bprints itself, and then currentbecomes X, which goes through the same checking process as Ydid, also realizing that its left subtree has been traversed, continuing with the Z. The rest of the tree follows the same pattern.

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

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.

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

回答by Maria Sakharova

The recursive in-order traversal is : (in-order(left)->key->in-order(right)). (this is similar to DFS)

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

When we do the DFS, we need to know where to backtrack to (that's why we normally keep a stack).

当我们做 DFS 时，我们需要知道回溯到哪里（这就是我们通常保留一个堆栈的原因）。

As we go through a parent node to which we will need to backtrack to -> we find the node which we will need to backtrack from and update its link to the parent node.

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

When we backtrack? When we cannot go further. When we cannot go further? When no left child's present.

我们什么时候回溯？当我们不能走得更远的时候。当我们不能更进一步？当没有留下孩子的礼物。

Where we backtrack to? Notice: to SUCCESSOR!

我们回溯到哪里？注意：给SUCCESSOR！

So, as we follow nodes along left-child path, set the predecessor at each step to point to the current node. This way, the predecessors will have links to successors (a link for backtracking).

因此，当我们沿着左子路径跟踪节点时，在每一步设置前驱节点指向当前节点。这样，前任将拥有与后继的链接（用于回溯的链接）。

We follow left while we can until we need to backtrack. When we need to backtrack, we print the current node and follow the right link to the successor.

我们尽可能地向左走，直到我们需要回溯。当我们需要回溯时，我们打印当前节点并按照正确的链接找到后继节点。

If we have just backtracked -> we need to follow the right child (we are done with left child).

如果我们刚刚回溯 -> 我们需要跟随右孩子（我们完成了左孩子）。

How to tell whether we have just backtracked? Get the predecessor of the current node and check if it has a right link (to this node). If it has - than we followed it. remove the link to restore the tree.

如何判断我们是否刚刚回溯？获取当前节点的前驱，并检查它是否有一个正确的链接（到这个节点）。如果它有 - 比我们遵循它。删除链接以恢复树。

If there was no left link => we did not backtrack and should proceed following left children.

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

Here's my Java code (Sorry, it is not C++)

这是我的 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;
}

回答by Ryan Burgert

I've made an animation for the algorithm here: https://docs.google.com/presentation/d/11GWAeUN0ckP7yjHrQkIB0WT9ZUhDBSa-WR0VsPU38fg/edit?usp=sharing

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

This should hopefully help to understand. The blue circle is the cursor and each slide is an iteration of the outer while loop.

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

Here's code for morris traversal (I copied and modified it from geeks for geeks):

这是莫里斯遍历的代码（我从 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)

回答by Adeath

public static void morrisInOrder(Node root) {
        Node cur = root;
        Node pre;
        while (cur!=null){
            if (cur.left==null){
                System.out.println(cur.value);      
                cur = cur.right; // move to next right node
            }
            else {  // has a left subtree
                pre = cur.left;
                while (pre.right!=null){  // find rightmost
                    pre = pre.right;
                }
                pre.right = cur;  // put cur after the pre node
                Node temp = cur;  // store cur node
                cur = cur.left;  // move cur to the top of the new tree
                temp.left = null;   // original cur left be null, avoid infinite loops
            }        
        }
    }

I think this code would be better to understand, just use a null to avoid infinite loops, don't have to use magic else. It can be easily modified to preorder.

我认为这段代码会更好理解，只需使用 null 以避免无限循环，不必使用其他魔法。它可以很容易地修改为预购。

回答by EXP

I hope the pseudo-code below is more revealing:

我希望下面的伪代码更具启发性：

node = root
while node != null
    if node.left == null
        visit the node
        node = node.right
    else
        let pred_node be the inorder predecessor of node
        if pred_node.right == null /* create threading in the binary tree */
            pred_node.right = node
            node = node.left
        else         /* remove threading from the binary tree */
            pred_node.right = null 
            visit the node
            node = node.right

Referring to the C++ code in the question, the inner while loop finds the in-order predecessor of the current node. In a standard binary tree, the right child of the predecessor must be null, while in the threaded version the right child must point to the current node. If the right child is null, it is set to the current node, effectively creating the threading, which is used as a returning point that would otherwise have to be on stored, usually on a stack. If the right child is notnull, then the algorithm makes sure that the original tree is restored, and then continues traversal in the right subtree (in this case it is known that the left subtree was visited).

参考问题中的 C++ 代码，内部 while 循环查找当前节点的有序前驱。在标准二叉树中，前驱的右孩子必须为空，而在线程版本中，右孩子必须指向当前节点。如果右孩子为空，则将其设置为当前节点，从而有效地创建threading，该线程用作返回点，否则必须存储在堆栈中。如果右子树不为空，则算法确保恢复原始树，然后继续在右子树中遍历（在这种情况下，已知左子树已被访问）。

回答by AshishR

I found a very good pictorial explanation of Morris Traversal.

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

回答by Manish Chauhan

Python Solution Time Complexity : O(n) Space Complexity : O(1)

Python 解决方案时间复杂度：O(n) 空间复杂度：O(1)

Excellent Morris Inorder Traversal Explanation

优秀的莫里斯中序遍历解释

class Solution(object):
def inorderTraversal(self, current):
    soln = []
    while(current is not None):    #This Means we have reached Right Most Node i.e end of LDR traversal

        if(current.left is not None):  #If Left Exists traverse Left First
            pre = current.left   #Goal is to find the node which will be just before the current node i.e predecessor of current node, let's say current is D in LDR goal is to find L here
            while(pre.right is not None and pre.right != current ): #Find predecesor here
                pre = pre.right
            if(pre.right is None):  #In this case predecessor is found , now link this predecessor to current so that there is a path and current is not lost
                pre.right = current
                current = current.left
            else:                   #This means we have traverse all nodes left to current so in LDR traversal of L is done
                soln.append(current.val) 
                pre.right = None       #Remove the link tree restored to original here 
                current = current.right
        else:               #In LDR  LD traversal is done move to R  
            soln.append(current.val)
            current = current.right

    return soln

回答by Dishant Batra

PFB Explanation of Morris In-order Traversal.

莫里斯中序遍历的 PFB 解释。

  public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
        {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class MorrisTraversal
    {
        public static IList<int> InOrderTraversal(TreeNode root)
        {
            IList<int> list = new List<int>();
            var current = root;
            while (current != null)
            {
                //When there exist no left subtree
                if (current.left == null)
                {
                    list.Add(current.val);
                    current = current.right;
                }
                else
                {
                    //Get Inorder Predecessor
                    //In Order Predecessor is the node which will be printed before
                    //the current node when the tree is printed in inorder.
                    //Example:- {1,2,3,4} is inorder of the tree so inorder predecessor of 2 is node having value 1
                    var inOrderPredecessorNode = GetInorderPredecessor(current);
                    //If the current Predeccessor right is the current node it means is already printed.
                    //So we need to break the thread.
                    if (inOrderPredecessorNode.right != current)
                    {
                        inOrderPredecessorNode.right = null;
                        list.Add(current.val);
                        current = current.right;
                    }//Creating thread of the current node with in order predecessor.
                    else
                    {
                        inOrderPredecessorNode.right = current;
                        current = current.left;
                    }
                }
            }

            return list;
        }

        private static TreeNode GetInorderPredecessor(TreeNode current)
        {
            var inOrderPredecessorNode = current.left;
            //Finding Extreme right node of the left subtree
            //inOrderPredecessorNode.right != current check is added to detect loop
            while (inOrderPredecessorNode.right != null && inOrderPredecessorNode.right != current)
            {
                inOrderPredecessorNode = inOrderPredecessorNode.right;
            }

            return inOrderPredecessorNode;
        }
    }