CIS 125

21 Binary Trees

 

 

In exercises 1-3, draw a graph having the following properties, or explain why no such graph exists.

 

1. Full binary tree; four internal vertices, five terminal vertices.

 

 

 

 

 

 

 

 

 

 

 

 

2. Full binary tree; height=3; nine terminal vertices.

 

 

 

 

 

 

 

 

 

 

 

 

3. Full binary tree; height=4; nine terminal vertices.

 

 

 

 

 

 

 

 

 


In exercises 4-8, list the order in which the vertices are processed using preorder (pre-fix), inorder(in-fix) and postorder (post-fix) traversal.

 

4.

 

5.

 

6.

 

 


7.

 

 

 

8.