CS
202 Fundamental Structures of Computer Science II
Assignment 2 – Binary Search Trees
Due Date: July 5, 2010 (Monday)
Question-1 (10 points)
What are the preorder, inorder, and postorder traversals of the following binary tree.
Question-2 (10 points)
a) Beginning with an empty binary search tree, what binary search tree is
formed when you insert the following values in the order given?
40, 25, 15, 20, 45, 65, 30, 35, 5, 75, 55
b) What binary search tree is formed, when you delete the following values in the order given? Give the binary trees after each deletion.
45, 40
Question-3 (15 points)
What is the maximum number of
nodes that a non-empty binary tree can have at level h? Prove it by induction.
Question-4 (15 points)
Write a recursive C++ function to count the number of leaves in a binary tree.
Assume that a pointer-based implementation is used for the binary tree.
Question-5 (50 points)
Design a program that provides a way for you to store and retrieve telephone numbers.
Design a user interface that provides the following operations:
Add: Adds a person’s name and phone number to the phone book.
Delete: Deletes a given person’s name and phone number from the phone book, given only the name.
Find: Locates and prints a person’s phone number, given only the person’s name.
Change: Changes a person’s phone number, given the person’s name and new phone number.
Quit: Quits the application, after first saving the address book in a text file.
You can proceed as follows:
- Design and implement the class Person, which represents the name and phone number of a person. You will store the instances of this class in the phone book.
- Design and implement the class Book, which represents the phone book. The class should contain a binary search tree as a data member. This tree contains the people in the book. The name of a person should be the key field in a node of this binary search tree.
- Add member functions that use a text file (called as phonebook.txt ) to save and restore the tree from the text file when your program is started. .Each line of this text file contains the name of a person (a string) and his/her phone number.
- Design and implement the class UserInterface, which provides the program’s user interface.
Hand-in:
·
You should give
the hard copy of your homework that includes the solutions of all of the
questions during the class hour on the due date. Make sure that your homework
must be a printer output with your names, and student ids on them; otherwise it
will not be graded.
·
You should also
send an email message to your TA, Sefa Kılıç (sefak@cs.bilkent.edu.tr), attaching with one zipped file
(named as yournameyourlastname.zip )
which contains:
1. A Word
file containing your homework (hw2.doc) and
2. Another file (hw2Q5.cpp) containing source code of
your C++ program in Question-5.
3. Make sure that the subject field of your email is
“CS202 HW2”. You should send this email message before 6:00 pm on
the due date. Do not forget to put your name in the header comment in your
program.
· Do not forget to put your name in the header comments in both hw02.cpp and hw02.h.
· You are free to write your programs in any environment (you may use either Linux or Windows). On the other hand, we will test your programs on “dijkstra.ug.bcc.bilkent.edu.tr” and we will expect your programs to compile and run on the “dijkstra” machine. If we could not get your program properly work on the “dijkstra” machine, you would lose a considerable amount of points. Therefore, we recommend you to make sure that your program compiles and properly works on “dijkstra.ug.bcc.bilkent.edu.tr” before submitting your assignment.
· Keep all the files before you receive your grade.
DO
IT YOURSELF. CHEATING WILL BE HEAVILY PUNISHED.