本文概述
使用Morris遍历，我们无需使用栈和递归就可以遍历树。Morris遍历的思想是基于线程二叉树的。在这个遍历过程中，我们首先创建到Inorder继承者的链接，并使用这些链接打印数据，最后恢复更改以恢复原始树。
1. Initialize current as root
2. While current is not NULL
If the current does not have left child
a) Print current’s data
b) Go to the right, i.e., current = current->right
Else
a) Make current as the right child of the rightmost
node in current's left subtree
b) Go to this left child, i.e., current = current->left尽管通过遍历对树进行了修改, 但在完成后将其恢复为原始形状。不像基于栈的遍历, 此遍历不需要额外的空间。
C++
#include <stdio.h>
#include <stdlib.h>
/* A binary tree tNode has data, a pointer to left child
and a pointer to right child */
struct tNode {
int data;
struct tNode* left;
struct tNode* right;
};
/* Function to traverse the 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 the right child of its inorder
predecessor */
if (pre->right == NULL) {
pre->right = current;
current = current->left;
}
/* Revert the changes made in the 'if' part to restore
the original tree i.e., fix the right child
of predecessor */
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 */
}
/* UTILITY FUNCTIONS */
/* Helper function that allocates a new tNode with the
given data and NULL left and right pointers. */
struct tNode* newtNode( int data)
{
struct tNode* node = new tNode;
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
/* Driver program to test above functions*/
int main()
{
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
struct tNode* root = newtNode(1);
root->left = newtNode(2);
root->right = newtNode(3);
root->left->left = newtNode(4);
root->left->right = newtNode(5);
MorrisTraversal(root);
return 0;
}Java
// Java program to print inorder traversal without recursion and stack
/* A binary tree tNode has data, a pointer to left child
and a pointer to right child */
class tNode {
int data;
tNode left, right;
tNode( int item)
{
data = item;
left = right = null ;
}
}
class BinaryTree {
tNode root;
/* Function to traverse a binary tree without recursion and
without stack */
void MorrisTraversal(tNode root)
{
tNode current, pre;
if (root == null )
return ;
current = root;
while (current != null ) {
if (current.left == null ) {
System.out.print(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;
}
/* Revert the changes made in the 'if' part to restore the
original tree i.e., fix the right child of predecessor*/
else {
pre.right = null ;
System.out.print(current.data + " " );
current = current.right;
} /* End of if condition pre->right == NULL */
} /* End of if condition current->left == NULL*/
} /* End of while */
}
public static void main(String args[])
{
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
BinaryTree tree = new BinaryTree();
tree.root = new tNode( 1 );
tree.root.left = new tNode( 2 );
tree.root.right = new tNode( 3 );
tree.root.left.left = new tNode( 4 );
tree.root.left.right = new tNode( 5 );
tree.MorrisTraversal(tree.root);
}
}
// This code has been contributed by Mayank Jaiswal(mayank_24)Python 3
# Python program to do Morris inOrder Traversal:
# inorder traversal without recursion and without stack
class Node:
"""A binary tree node"""
def __init__( self , data, left = None , right = None ):
self .data = data
self .left = left
self .right = right
def morris_traversal(root):
"""Generator function for iterative inorder tree traversal"""
current = root
while current is not None :
if current.left is None :
yield current.data
current = current.right
else :
# Find the inorder predecessor of current
pre = current.left
while pre.right is not None and pre.right is not current:
pre = pre.right
if pre.right is None :
# Make current as right child of its inorder predecessor
pre.right = current
current = current.left
else :
# Revert the changes made in the 'if' part to restore the
# original tree. i.e., fix the right child of predecessor
pre.right = None
yield current.data
current = current.right
# Driver program to test the above function
"""
Constructed binary tree is
1
/ \
2 3
/ \
4 5
"""
root = Node( 1 , right = Node( 3 ), left = Node( 2 , left = Node( 4 ), right = Node( 5 )
)
)
for v in morris_traversal(root):
print (v, end = ' ' )
# This code is contributed by Naveen Aili
# updated by Elazar GershuniC#
// C# program to print inorder traversal
// without recursion and stack
using System;
/* A binary tree tNode has data, pointer to left child
and a pointer to right child */
class BinaryTree
{
tNode root;
public class tNode
{
public int data;
public tNode left, right;
public tNode( int item)
{
data = item;
left = right = null ;
}
}
/* Function to traverse binary tree without
recursion and without stack */
void MorrisTraversal(tNode root)
{
tNode current, pre;
if (root == null )
return ;
current = root;
while (current != null )
{
if (current.left == null )
{
Console.Write(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;
}
/* Revert the changes made in
if part to restore the original
tree i.e., fix the right child
of predecssor*/
else
{
pre.right = null ;
Console.Write(current.data + " " );
current = current.right;
} /* End of if condition pre->right == NULL */
} /* End of if condition current->left == NULL*/
} /* End of while */
}
// Driver code
public static void Main(String []args)
{
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
BinaryTree tree = new BinaryTree();
tree.root = new tNode(1);
tree.root.left = new tNode(2);
tree.root.right = new tNode(3);
tree.root.left.left = new tNode(4);
tree.root.left.right = new tNode(5);
tree.MorrisTraversal(tree.root);
}
}
// This code has been contributed
// by Arnab Kundu输出如下：
4 2 5 1 3时间复杂度：O(n)，如果仔细观察, 会发现树的每个边缘最多被遍历两次。在最坏的情况下, 会创建和删除相同数量的额外边(与输入树一样)。
参考文献：
www.liacs.nl/~deutz/DS/september28.pdf
www.scss.tcd.ie/disciplines/software_systems/…/HughGibbonsSlides.pdf
如果你在上述代码/算法中发现任何错误, 或者想共享有关栈Morris有序树遍历的更多信息, 请写评论。
