解释 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

我知道这个树的修改方式是 current node，是 right subtree中 max node的 right child，并且使用这个属性进行无序遍历。但除此之外，我就迷失了。

编辑: 找到了附带的 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 */
}
56333 次浏览
小开
最佳答案

如果我没有看错算法的话，这应该是一个例子来说明它是如何工作的:

     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。树的其余部分遵循相同的模式。

不需要递归，因为返回到(sub)树根的链接不再依赖于通过堆栈的回溯，而是被移动到一个递归的无序树遍历算法可以访问的位置——在其左边的子树完成之后。

小开

我希望下面的伪代码更能说明问题:

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，那么算法确保恢复了原始树，然后继续遍历右边的子树(在这种情况下，已知访问了左边的子树)。

小开 
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 来避免无限循环，不必使用 magic else。它可以很容易地修改为预订。

小开

递归顺序遍历是: (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;
}
小开

我在这里为算法做了一个动画: Https://docs.google.com/presentation/d/11gwaeun0ckp7yjhrqkib0wt9zuhdbsa-wr0vspu38fg/edit?usp=sharing

Animation of Morris traversal algorithm

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

下面是 Morris 遍历的代码(我从极客那里复制并修改了它) :

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)
小开

我发现了一个非常好的图解 莫里斯 · 特拉维斯。

Morris Traversal

小开

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

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

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
小开

Morris 顺序遍历的 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;
}
}

提交答案