Morris traversal

Posted on In Views:

Morris (InOrder) traversal is a tree traversal algorithm that does not employ the use of recursion or a stack. In this traversal, links are created as successors and nodes are printed using these links. Finally, the changes are reverted back to restore the original tree.

Algorithm

  • Initialize the root as the current node curr.
  • While curr is not NULL, check if curr has a left child.
  • If curr does not have a left child, print curr and update it to point to the node on the right of curr.
  • Else, make curr the right child of the rightmost node in curr's left subtree.
  • Update curr to this left node.

Demo

Let’s take the binary tree given below and traverse it using Morris (InOrder) traversal.

4 is the root, so it is initialized as curr. 4 has a left child, so it is made the rightmost right child of it’s left subtree (the immediate predecessor to 4 in an InOrder traversal). Finally, 4 is made the right child of 3 and curr is set to 2.

The {2} above refers to 2 and all of its children. Now that the tree has a link back to 4, the traversal continues.

1 is printed because it has no left child and curr is returned to 2, which was made to be 1's right child in the previous iteration. On the next iteration, 2 has both children. However, the dual-condition of the loop makes it stop when it reaches itself; this is an indication that its left subtree has already been traversed. So, it prints itself and continues with its right subtree (3). 3 prints itself, and curr becomes 4 and goes through the same checking process that 2 did. It also realizes that its left subtree has been traversed and continues with the 5. The rest of the tree follows this same pattern.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Node { 
	int data; 
	Node left_node, right_node; 

	Node(int item) 
	{ 
		data = item; 
		left_node =  null;
		right_node = null; 
	} 
} 

class Tree { 
	Node root; 

	void Morris(Node root) 
	{ 
		Node curr, prev; 

		if (root == null) 
			return; 

		curr = root; 
		while (curr != null) { 
			if (curr.left_node == null) { 
				System.out.print(curr.data + " "); 
				curr = curr.right_node; 
			} 
			else { 
				/* Find the previous (prev) of curr */
				prev = curr.left_node; 
				while (prev.right_node != null && prev.right_node != curr) 
					prev = prev.right_node; 

				/* Make curr as right child of its prev */
				if (prev.right_node == null) { 
					prev.right_node = curr; 
					curr = curr.left_node; 
				} 

				/* fix the right child of prev*/

				else { 
					prev.right_node = null; 
					System.out.print(curr.data + " "); 
					curr = curr.right_node; 
				} 

			} 

		}
	} 

	public static void main(String args[]) 
	{ 
		
		Tree tree = new Tree(); 
		tree.root = new Node(4); 
		tree.root.left_node = new Node(2); 
		tree.root.right_node = new Node(5); 
		tree.root.left_node.left_node = new Node(1); 
		tree.root.left_node.right_node = new Node(3); 

		tree.Morris(tree.root); 
	} 
}

转自：https://www.educative.io/answers/what-is-morris-traversal