解释不使用堆栈或递归的Morris有序树遍历
有没有人能帮我理解一下不使用堆栈或递归的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 */
}回答 6
Stack Overflow用户
发布于 2011-04-01 05:31:46
如果我没看错算法，这应该是一个它是如何工作的例子：
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的右子节点被设为A的右子节点。在下一次迭代中，Y有两个孩子。然而，循环的双重条件使它在到达自身时停止，这表明它的左子树已经被遍历了。所以，它打印自己，并继续它的右子树，即B。
B打印它自己，然后current变成X，它经历了与Y相同的检查过程，也意识到它的左子树已经被遍历，继续Z。树的其余部分遵循相同的模式。
不需要递归，因为返回(子)树的根的链接被移动到递归有序树遍历算法中无论如何都会被访问的点--在它的左子树完成之后，而不是依赖于通过堆栈回溯。
Stack Overflow用户
发布于 2015-02-27 18:54:21
递归的顺序遍历是：(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;
}Stack Overflow用户
发布于 2019-10-02 04:25:16
我在这里为算法制作了一个动画：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)https://stackoverflow.com/questions/5502916
复制相似问题