CSCI 132 Data Structures--Spring 2014

Assignment 9 Solutions

Part 1. Programming Binary Tree Functions

Solution to binary tree functions

Part 2. Working with Binary Trees

1. Determine the order in which the vertices of the following binary tree will be visited under (1) preorder, (2) inorder, and (3) postorder traversal.

Preorder: 1 2 4 7 3 5 6 8 9

 

Inorder: 4 7 2 1 5 3 8 6 9

 

Postorder: 7 4 2 5 8 9 6 3 1

 

2. Draw expression trees for each of the following expressions, and show the order of visiting the vertices in (1) preorder, (2) inorder, and (3) postorder:

(a) log n!

Tree:



Preorder: log ! n

Inorder: log n !

Postorder: n ! log

 

(b) (a - b) - c

Tree:



Preorder: - - a b c

Inorder: a - b - c

Postorder: a b - c -

 

Problem 3 is based on the following binary search tree:

3. Insert each of the following keys into the preceding binary search tree. Draw the resulting Tree. Show the comparisons of keys that will be made in each case. Do each part independently, inserting the key into the original tree.

a) m

Tree:



Comparisons made:

m < k? false
m > k? true
m < n? true

b) f

Tree:



Comparisons made:

f < k? true
f < c? false
f > c? true
f < e? false
f > e? true
f < h? true

4. Drawthe binary search trees that function insert() will construct for the list of 14 names presented in the following order and inserted into a previously empty binary search tree.

Jan Guy Jon Ann Jim Eva Amy Tim Ron Kim Tom Roy Kay Dot

Tree: