Java Reference
In-Depth Information
There are three possible answers you might give. You can process the root before
you traverse either subtree, after you traverse both subtrees, or in between traversing
the two subtrees. These three approaches are known as preorder, postorder, and
inorder traversals respectively.
process the root
traverse left
subtree
traverse right
subtree
inorder
preorder
postorder
For example, consider the following simple tree:
7
6
5
A preorder traversal visits the root, then the left subtree, then the right subtree,
yielding the sequence [7, 6, 5] . An inorder traversal visits the left subtree, then the
root, then the right subtree, yielding the sequence [6, 7, 5] . A postorder traversal
visits the left subtree, then the right subtree, then the root, which yields [6, 5, 7] .
Notice in this example that we always list 6 before 5 (left before right) and that the
only value which changes position is the root value 7 .
When we traverse a more complex tree, we simply use the recursive nature of this
definition to carry out the traversal. For example, consider the following tree.
2
0
3
7
1
9
6
5
8
4
The overall root stores the value 2 , so we know that the different traversals will
look like this:
Preorder traversal: [2, <left> , <right> ]
Inorder traversal: [ <left> , 2, <right> ]
Postorder traversal: [ <left> , <right> , 2]
 
Search WWH ::




Custom Search