Traversing Binary Trees

Traversing Binary Trees

Visual Studio 6.0

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.

Inorder Traversal

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 k

Preorder Traversal

Using 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 j

Postorder Traversal

Using 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

© 1997 by SYBEX Inc. All rights reserved.

Show:
© 2016 Microsoft