Discrete Mathematics for Computer Science

386 CHAPTER 6 Graph Theory

VERTEX LABEL LISTINGS

r

left child /• * right child

T 2

PREORDER

1. List the label at the root vertex r of T.


2. If T 1 is nonempty, list the labels of the vertices of T 1 in preorder.


3. If T 2 is nonempty, list the labels of the vertices of T2 in preorder.
   INORDER


4. If T 1 is nonempty, list the labels of the vertices of T 1 in inorder.


5. List the label of the root vertex r of T.


6. If T2 is nonempty, list the labels of the vertices of T 2 in inorder.
   POSTORDER


7. If T 1 is nonempty, list the labels of the vertices of TI in postorder.


8. If T2 is nonempty, list the labels of the vertices of T 2 in postorder.


9. List the label of the root vertex r of T.

Figures 6.49 and 6.50 illustrate inorder listings.

milk

• -'•soda 5 5,
  cereal' , • soda
  7',,/7',
  banana" ,/ 7 4 grape 6 88

1 ,,,, orange water

fruit^3

Figure 6.50 Inorder traversal.

In Figure 6.50, the tree shown is a binary search tree. The word fruit is listed by the

inorder traversal before grape, because the inorder process lists the label of the left subtree

before listing the label at the vertex itself and, finally, lists the labels in the right subtree of

that vertex. In this example, the vertex labeled grape has no right subtree, so this finishes

the listing of the labels in the right subtree labeled cereal (already listed). This in turn

completes the listing of the labels in the left subtree of the vertex labeled milk. So, the next

label listed is milk.