CS 112 B1 - Spring 2003: Homework 4

Due Thursday, March 6 at 11:59 P.M.

Please keep in mind the policy on collaboration, as described on the syllabus.

Your code will be graded for style as well as correctness and should conform to the following style guidelines.

PROBLEM 1:

The goal is to augment the strings program from HW 3. Specifically, the changes are as follows: we can now search for a strings (using the command f followed by the string), which will tell us whether the string is in the tree, and remove a string from a tree (using the command r followed by the string). Remove should output an error if the string is not found in the tree. We have provided most of the functionality for you. In fact, the only part you have to write is a portion of the function that deletes a string from a tree. Furthermore, we have augmented PrintAscending and PrintDescending with information on whether we are going up or down in the tree, to help you debug your code. For the same reason, the f command prints not only whether a string is in the tree, but also its location (R for root, R0 for left child of root, R1 for right child of root, and so on). For example,
? Boston
? Denver
? Chicago
? Cincinnati
? Brownsfield
? Albuquerque

a
v v v v v v v v v
v v v v v v v v v
Albuquerque
^ ^ ^ ^ ^ ^ ^ ^ ^
Boston
v v v v v v v v v
v v v v v v v v v
v v v v v v v v v
Brownsfield
^ ^ ^ ^ ^ ^ ^ ^ ^
Chicago
v v v v v v v v v
Cincinnati
^ ^ ^ ^ ^ ^ ^ ^ ^
^ ^ ^ ^ ^ ^ ^ ^ ^
Denver
^ ^ ^ ^ ^ ^ ^ ^ ^
^ ^ ^ ^ ^ ^ ^ ^ ^

f Denver
Found in location R1
f Cincinnati
Found in location R101
f Seattle
Not Found



We provide you with two files:

• strings2.o, which contains most of the functionality (you cannot see its source code)
• strings2r.cpp, which contains a half-empty function for removing nodes from the tree.