Once you’ve created a binary tree, you can use one of three standard methods for traversing the tree. All three of the following examples use the tree illustrated in Figure 6.32. In that figure, the nodes contain letters, but their ordering here doesn’t mean anything. They’re just labeled to make it easy to refer to them.
Figure 6.32: Use this binary tree to demonstrate treetraversal.
To traverse a tree using inorder traversal, you must visit the left subtree, then the root node, and then the right subtree. When visiting the subtrees, you take the same steps. If, each time you visited a root node in the tree shown in Figure 6.32, you listed the value, you’d list the nodes in the following order:
a b c d e f g h i j kUsing preorder traversal, you first visit the root node, then the left subtree, and then the right subtree. Using this method, you’ll always print out the root value and then the values of the left and right children. Using the example shown in Figure 6.32, you’d print the nodes in this order:
f b a d c e i h g k jUsing postorder traversal, you visit the left subtree, then the right subtree, and finally, the root node. Using the example shown in Figure 6.32, you’d visit the nodes in this order:
a c e d b g h j k i f