In this section algorithms are developed for traversing trees and are applied to two examples. The second example should be studied carefully, because it illustrates an important modified traversal of trees that has many applications. Assuming the trees are ordered, it makes sense to refer to a tree's first subtree, second subtree, and so on. If an order is not given, the programmer can impose one.
When trees are used to store data at their nodes, then tree traversals give a means to access all the data. However, a tree might be used to represent a maze or all routes from Philadelphia to San Francisco. Traversal of the tree then provides the means to find exits from the maze or the shortest route across the country. The maze and the routes must not intersect. When they do, a more general data structure, a graph, is needed for their representation. Unlike trees, a graph allows more than one path between its nodes. * Should a tree contain family relationships by storing an individual's record at a node, a traversal allows the parent (predecessor) or the children (successors) of an individual to be found.
* It is not difficult to generalize tree traversal algorithms to obtain graph traversal algorithms.
The preorder and postorder traversals of binary trees generalize quite naturally to ordered trees.
To preorder traverse an ordered tree:
1. Access and process its root, then
2. Preorder traverse its subtrees in order.
To postorder traverse an ordered tree:
1. Postorder traverse its subtrees in order, then
2. Access and process its root.
There is no natural inorder traversal of trees. Preorder and postorder traversals of a tree correspond, respectively, to preorder and inorder traversals of its corresponding binary tree. The preorder and postorder access sequences for the tree of Figure 7.13(a) are ABEFGCHDIKLMJ and EFGBHCKLMIJDA. You should confirm that a preorder and an inorder traversal of the binary tree of Figure 7.13 result in these respective access sequences. A preorder traversal is also called a depth-first traversal.
7.6.1 Obtaining the Binary Tree for a Tree
7.6.2 Backtracking: The n-queens Problem