CMSC-341 Fall 2004

Project 3

Assigned	20 Oct 2004
Due	2 Nov 2004 at 11:59PM
Updates

Background

This project will give you practice working with binary search trees and with writing recursive functions.

Description

In this project you will write code to manipulate and compute properties of binary search trees.

Here are your tasks:

Obtain the files BinarySearchTree.h, BinarySearchTree.cpp, and dsexceptions.h from the following location:
/afs/umbc.edu/users/o/a/oates/pub/CMSC341/Proj3/
These files do not adhere to CS341 coding standards. You can use them "as is". That is, you do not need to edit them to bring them up to CS341 standards.
Write Proj3.cpp and any supporting files required to process command files.

Implement new BinarySearchTree methods required to process commands contained in command files.

Answer the questions posed in 341-Fall04-proj3_questions.txt. Copy the file

/afs/umbc.edu/users/o/a/oates/pub/CMSC341/Proj3/341-Fall04-p3_questions.txt

to your own directory and edit it to provide your answers to the questions. Don't forget to submit the edited file; it's 10% of this project's grade.

Definition of the ADT

This project simply requires that you be able to process the commands contained in a command file. Those commands load trees, manipulate trees (e.g., creating a tree that contains the union of the elements in two other trees), and compute properties of trees (e.g., whether a given tree is a complete tree). You may implement any new classes that you need to complete the project. Most of the code for this project, however, will revolve around opening, reading, and closing the command file, and manipulating and computing properties of trees.

Most of the commands will require that you implement a recursive BinarySearchTree method. As with many of the existing BST methods, you will probably want a public method that simply calls a private method, where the private method is recursive and the public method is not. See the author's implementation of insert for an example of this. Your recursive methods can call helper functions and take as many arguments as you deem necessary.

The Command Line

Project 3 will be invoked with a command line that consists of one argument - the name of a file that contains a set of operations that must be performed. The format of this file is described in the command file section below.

Note that you must check command line arguments to ensure that they are valid, e.g. that the command file can be opened, and print an appropriate message if an error is found.

The Command File

Commands in the file specify operations to be performed. Each line in the file represents one command. Blank lines may appear anywhere in the file and should be ignored. Otherwise, you can assume that any line containing a command is syntactically well-formed. We make this assumption so you don't have to spend lots of time making the command file parser bullet proof.

Echo each command as it is read.

All of the commands below refer to trees by names that are strings. When creating a tree, you must ensure that a tree with the same name does not already exist. If it does, print an error message and proceed to the next command. When a command refers to an existing tree by name, you must ensure that a tree with that name does in fact exist. If not, print an error message and proceed to the next command.

You cannot add a NAME data member to the BinarySearchTree class.

The command file format follows:

TREE NAME N V1 V2 ... VN - This command asks you to create a binary search tree named NAME (a string without any white space). The tree contains N nodes, and the N integer values to be stored in the tree are given as part of the command (V1 V2 ... VN). Read each value and insert it into the tree in the order in which it was read. The value -1 will never be specified as one of the Vi.

SAME_SHAPE NAME1 NAME2 - Print a message indicating whether the trees named NAME1 and NAME2 have the same shape. That is, ignoring node values, are they identical to one another? Your solution for this command must involve recursion, and there must be a public BinarySearchTree method, i.e., same_shape, that takes another binary search tree as an argument and returns a boolean value.

PERFECT NAME - Print a message indicating whether the tree named NAME is a perfect tree. Your solution must involve recursion.

COMPLETE NAME - Print a message indicating whether the tree named NAME is a complete tree. Your solution must involve recursion.

IPL NAME - Print a message indicating the internal path length of the tree named NAME. Your solution must involve recursion.

EPL NAME - Print a message indicating the external path length of the tree named NAME. Your solution must involve recursion.

UNION NEW_NAME NAME1 NAME2 - Create a tree named NEW_NAME that contains the union of the elements in the trees named NAME1 and NAME2. It is OK if both trees contain the same value, but it should only occur once in the newly created tree. Your solution must involve a public BST method that takes another tree as an argument. Neither of the trees that are unioned should be modified.

INTERSECTION NEW_NAME NAME1 NAME2 - Create a tree named NEW_NAME that contains only those values that are in the tree named NAME1 and the tree named NAME2.Your solution must involve a public BST method that takes another tree as an argument. Neither of the trees that are interesected should be modified.

PRINT NAME - Print the contents of the tree named NAME using an inorder traversal.

Sample Output

The following input file:

TREE amy 3 20 10 30
TREE bob 3 10 5 15
PERFECT amy
PERFECT bob
UNION carl amy bob
PRINT carl

creates the following output:

Command: TREE amy 3 20 10 30

Command: TREE bob 3 10 5 15

Command: PERFECT amy

amy is perfect

Command: PERFECT bob

bob is perfect

Command: UNION carl amy bob

Command: PRINT carl

5 10 15 20 30

Files To Be Submitted

Submit all files required to build an executable named Proj3 by running make.

Submit the files using the procedure given to you for your section of the course.
If your makefile is set up correctly, you should be able to execute the command make submit.

Submit Tools

There are a number of tools available to you to check on your submittal. It is your responsibility to ensure that the submittal is correct and will result in a successful
compilation of your project. Do not wait till the last minute to submit your files. Give yourself enough time to check that your submittal is correct.

If you don't submit a project correctly, you will not get credit for it. Why throw away all that hard work you did to write the project? Check your
submittals. Make sure they work. Do this before the due date.

Documentation for the submit program is on the web at http://www.gl.umbc.edu/submit/. One of the tools provided by the submit program is
submitls. It lists the names of the files you have submitted.

Additionally, there are two programs for use only by CMSC-341 students (not part of the UCS submit program). They are in the directory
/afs/umbc.edu/users/o/a/oates/pub/CMSC341/ and are named submitmake and submitrun. You can use these programs to
make or run your submitted projects.

The syntax is similar to that for submit:

submitmake <class> <project>

Example: submitmake cs341 Proj1

This makes the project, and shows you the report from the make utility. It cleans up the directory after making the project (removes .o and ii_files), but leaves the
executable in place.

submitrun <class> <project> [command-line args]

Example: submitrun cs341Proj1 checkers checkfile.dat

This runs the project, assuming there is an executable (i.e. submitmake was run successfully).

Grading and Academic Integrity

Your project will be tested using a variety of command lines, some of which will be invalid.
Your project will also be tested using a variety of command files which will test various conditions which your code should handle.

Project grading is described in the Project Policy handout.

Your answers to 341-Fall04-proj1_questions.txt are worth 10% of your project grade.

Cheating in any form will not be tolerated. Please re-read the Project Policy handout for further details on honesty in doing projects for this course.

Remember, the due date is firm. Submittals made after midnight of the due date will not be accepted. Do not submit any files after that time.