Morris traversal
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 nodecurr
. - While
curr
is notNULL
, check ifcurr
has a left child. - If
curr
does not have a left child, printcurr
and update it to point to the node on the right ofcurr
. - Else, make
curr
the right child of the rightmost node incurr
'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 | class Node { |
转自:https://www.educative.io/answers/what-is-morris-traversal