不使用栈或递归，解释 Morris 中序遍历二叉树的方法

Question

请问有没有人能够在不使用栈或递归的情况下帮助我理解 Morris 中序遍历算法？我一直在尝试理解它的工作原理，但它总是让我无法理解。

 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

我理解树是以这样的方式进行修改的：当前节点变为右子树中最大节点的右子节点，并且可以利用此属性进行中序遍历。但除此之外，我不知道其他了。

编辑： 找到了这段伴随的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 */
}

- brainydexter

---

我以前从未听说过这个算法。相当优雅！ - Fred Foo

我认为指出伪代码+代码的来源可能会很有用（据推测）。 - Bernhard Barker

无递归和无栈的中序遍历二叉树 - DebashisDeb

在上述代码中，以下行不是必需的：pre->right = NULL; - prashant.kr.mod

我认为伪代码存在一个重要的遗漏错误。在“Else”的步骤“a”中，它说要标记current的前任并向左移动。这应该说得更像是“如果我们在查找其自身前任时撞到了current，则取消线程（可选，如果您不想保留树线程）并向右移动”。我认为这就是@Talonj在他们出色的答案中所说的“循环的双重条件”。这里的教训是代码胜过描述。 - bronzenose

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，因为它没有左子节点，并返回给Y，在上一次迭代中将A作为它的右子节点。在下一次迭代中，Y有两个子节点。但是循环的双重条件使得它停止到达自己时，这表明其左子树已经被遍历过了。所以，它打印出自己，并继续其右子树，即B。

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

不需要递归，因为不是依靠堆栈的回溯而是链接回到（子）树的根移动到递归中序遍历算法访问它的位置 -- 在其左子树完成之后。

- Talonj

---

感谢您的解释。左子节点并没有被切断，相反，在遍历树的目的下，新的右子节点被添加到最右侧的叶子节点后，树会随后被恢复。请查看我的更新帖子，并附上代码。 - brainydexter

不错的草图，但我仍然不理解while循环条件。为什么要检查pre->right！= current呢？ - No_name

我不明白为什么这个方法有效。在打印 A 之后，Y 成为了根节点，而你还是有 A 作为左子节点。因此，我们面临的情况与之前相同，接着我们又重复了 A。实际上，看起来像一个无限循环。 - user678392

这难道不会切断Y和B之间的连接吗？当X被设置为当前节点，而Y被设置为前一个节点时，程序将会沿着前一个节点的右子树一直查找到当前节点（X），然后将pre=>right设置为NULL，这个节点应该是B，对应上面发布的代码。 - Achint

感谢您的简单解释。 - Jimit.Gandhi

Answer 2

递归中序遍历的顺序为：(中序遍历(左子树)->关键字->中序遍历(右子树))。（类似于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;
}

- Maria Sakharova

---

我很喜欢你的答案，因为它提供了高层次的推理来解决问题！ - KFL

急需一张图示。 - NoName

Answer 3

我已经为该算法制作了一段动画： https://docs.google.com/presentation/d/11GWAeUN0ckP7yjHrQkIB0WT9ZUhDBSa-WR0VsPU38fg/edit?usp=sharing

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

以下是Morris遍历的代码（我从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)

- Ryan Burgert

---

你的动画非常有趣。请考虑将其制作成图片并加入到你的帖子中，因为外部链接通常随着时间的推移而失效。 - laancelot

动画很有帮助！ - yyFred

很棒的电子表格和二叉树库的使用。但是代码不正确，无法打印根节点。你需要在“pre.right = None”行后添加“print(cursor.value)”。 - satnam

Answer 4

我发现了一篇非常好的有关Morris遍历的图解：链接。图片如下：。

- Ashish Ranjan

---

仅提供链接的答案在未来链接失效时将失去其价值，请将链接中的相关内容添加到答案中。 - Arun Vinoth-Precog Tech - MVP

当然，我很快就会添加它。 - Ashish Ranjan

Answer 5

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

我认为这段代码可以更易于理解，只需使用null来避免无限循环，不必使用神奇的else。它可以很容易地修改为前序。

- Adeath

---

解决方案非常简洁，但存在一个问题。根据Knuth的说法，在最后不应修改树。通过执行 temp.left = null，将会丢失整棵树。 - Ankur

这种方法可以用于将二叉树转换为链表等场合。 - cyber_raj

就像@Shan所说的那样，算法不应该改变原始树。虽然您的算法可以遍历它，但它会破坏原始树。因此，这实际上与原始算法不同，因此具有误导性。 - ChaoSXDemon

Answer 6

我希望以下伪代码更容易理解：

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

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

- EXP

Answer 7

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

优秀的Morris中序遍历解释

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

- Manish Chauhan

---

很抱歉，但这不是直接回答问题的答案。OP要求解释它的工作原理，而不是实现，可能是因为他们想自己实现算法。您的评论对于已经了解算法的人很好，但OP还没有理解。此外，作为一项政策，答案应该是自包含的，而不仅仅是链接到某些外部资源，因为链接可能会随着时间的推移而改变或中断。包含链接是可以的，但如果您这样做，您也应该至少包括链接提供的要点。 - Anonymous1847

Answer 8

解释 Morris 中序遍历。

  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;
        }
    }

- Dishant Batra