Discrete Mathematical Structures by Pearson

Trees 11-15

Example 1 Find preorder, inorder and postorder traversal for the positional tree shown in Fig. 11.16.

1

7

98

53

26

Figure 11.16

Solution:

(1) Preorder traversal output is 1–2–3–5–6–7–8–9

(2) Inorder traversal output is 3–2–5–1–6–8–7–9

(3) Postorder traversal output is 3–5–2–8–9–7–6–1

Example 2 Find preorder, inorder and postorder traversal outputs for the binary tree shown in

Fig. 11.17.

A

EF

G

KJ MLIH

D

BC

Figure 11.17

Preorder: A B D H I E J K C F G L M

Inorder: H D I J E K B A F C L G M

Postorder: H I D J K E B F L M G C A

11.5 BINARY SEARCH TREE

A binary tree T is called a binary search tree if the value at each vertex (NODE) is greater ...