7 . 1 B i n a ry Tr e e Tra v e r s a l s 159 1 a 2 3 b 4 5 6 c 7 d 8 9 10 11 12 e 13 14 f 15 g h Figure 7.1 node's value. You locate a value by starting at the root of the tree and turning left or right as required until you find the value or that the value is not in the tree. All tree indexing schemes, such as B-trees and B+-trees, generalize this idea to a traversal in a multiway tree. 7.1 Binary Tree Traversals One of the standard programs you have to write in freshman computer sci- ence is a traversal for a binary tree. A traversal is an orderly way of visiting every node so that you can perform some operation on it. There are three ways to traverse a binary tree, starting at the root. 1. Postorder traversal a. Recursively traverse the left son's subtree b. Recursively traverse the right son's subtree c. Visit the root of the current subtree In this sample tree, you would get the list (`B', `E', `D', `F', `G', `C', `A'). This algorithm can be generalized to nonbinary trees and is called a depth-first search. If you were given the parse tree for an infixed arithmetic expression, as shown in Figure 7.2, the postorder traversal would give you the reverse Polish notation equivalent of the expression. This algorithm can be generalized to nonbinary trees and is called a breadth-first search. 2. Preorder traversal a. Visit the root of the current subtree b. Recursively traverse the left son's subtree c. Recursively traverse the right son's subtree