Name:_______________________________

CSCI 132 Data Structures

Assignment 9 Answer Sheet

Home | | Syllabus | | Assignments | | Lecture Notes

Part 2. Working with Binary Trees

For each of the following problems, write your answer on this sheet.

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:

 

Inorder:

 

Postorder:

 

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:

Inorder:

Postorder:

 

(b) (a - b) - c

Tree:

 

 

 

 

 

Preorder:

Inorder:

Postorder:

 

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:

 

 

b) f

Tree:

 

 

 

 

 

 

Comparisons made:

 

 

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:

 

 

 

 

 

 

 

 

 

 

 

Turn in this sheet with your answers on it along with the rest of homework 9.

Home | | Syllabus | | Assignments | | Lecture Notes