We have seen examples whose solution includes a traversal through a collection of records in an array or a list. A traversal through a collection of records stored in a binary tree is also the basis for the solution to many problems. We will consider three distinct ways to traverse a binary tree: (1) preorder, (2) inorder, and (3)postorder.
Pre-, in-, and postorder traversals are often referred to mnemonically as root-left-right, left-root-right, and left-right-root traversals. The prefixes pre, in, and post refer to whether the root is accessed prior to, in between, or after the corresponding traversals of the left and right subtrees. In all cases, the left subtree is traversed before the right subtree. When nodes are listed in the order in which they are processed, all nodes in the left subtree appear before all nodes in the right subtree, no matter which traversal is used. However, the type of traversal determines where the root appears. Since we defined binary trees recursively, it is convenient to give recursive definitions for these traversals.
To preorder traverse a binary tree:
if the binary tree is not the null binary tree, then
1. access and process its root
2. traverse its left subtree in preorder
3. traverse its right subtree in preorder
To inorder traverse a binary tree:
if the binary tree is not the null binary tree, then
1. traverse its left subtree in inorder
2. access and process its root
3. traverse its right subtree in inorder
To postorder traverse a binary tree:
if the binary tree is not the null binary tree, then
1. traverse its left subtree in postorder
2. traverse its right subtree in postorder
3. access and process its root
Let's apply these definitions to Figure 7.6(b).
To do a preorder traversal of t, since it is not null, requires that its root, L, be accessed and processed first. Next, the left subtree of t must be preorder traversed. Applying the definition to it, its root, O, is accessed and processed. Since O's left subtree is null, its right subtree is traversed next in preorder. This results in C being accessed and processed, terminating the preorder traversal of O's right subtree and also of t's left subtree. Completing t's traversal requires a preorder traversal of its right subtree, resulting in U, S, and T being accessed and processed in turn.
An inorder traversal of t requires its left subtree to be inorder traversed first. Applying the definition to this left subtree requires its null left subtree to be inorder traversed (note how easy that is), its root O to be accessed and processed next, and then its right subtree to be inorder traversed, which results in C being accessed and processed. This terminates the inorder traversal of t's left subtree. T's root, L, must then be accessed and processed, followed by an inorder traversal of t's right subtree. This causes S, U, and T to be accessed and processed in turn, completing the inorder traversal of t.
Try applying the postorder traversal definition to t yourself. The sequences below represent the order in which the records stored at the nodes of t are accessed and processed for each of the traversals.
Notice that the terminal nodes C, S, and T are dealt with in the same order for all three traversals. This is not just a coincidence but will always happen.
The trees of Figure 7.7 represent a table of contents, an arithmetic expression, and a program that invokes functions that, in turn, invoke other functions. Traversing these trees, respectively, in pre-, in-, and postorder results in the order of access to nodes shown in Figure 7.7(d-f). Each is a natural application of one of the three traversals: a listing of the table of contents, an arithmetic expression in the usual notation, and a listing of the order in which the functions are needed to test another function (for example, P1 and P2 are needed to test P3).
Not all data structures need to be traversed. For example, stacks, queues, heaps, and the hash tables to be introduced in Chapter 9 are not normally traversed. Just as applications of arrays and, even more so, lists often reduce to traversals, applications of binary trees often do as well. Therefore procedures for their traversal merit study.
locust
oclsut
costul