CMSC 341 Spring 2007

Project 3

Assigned	Monday, March 26, 2007
Due	Sunday, April 8, 2007 at 11:59pm
Updates	26 March 2007 The original description of PRINT indicated that the BST should be printed using an in-order traversal. That is incorrect. Per the sample output, PRINT should output the tree using a level order traversal. The original level-order output of "carl" was incorrect and has been corrected.

Background

This project will give you practice working with binary search trees (BSTs), BST iterators, and with writing recursive functions.

Description

In this project you will read a command file to create and manipulate BSTs. You will write functions (some of which are recursive) to determine if two BSTs have the same shape, form the union of two BSTs, form the intersection of two BSTs, and to determine if a BST has certain properties.

You will be provided with the author's BST code as a base. You will also be required to implement one or more BST iterators as discussed in class. You will of course need to write code to read the command file and execute the commands within.

Most of the commands will require that you implement a recursive BST 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.

Here are your tasks:

Copy the author's BST code from Mr. Frey's public directory
/afs/umbc.edu/users/f/r/frey/pub/CMSC341/Proj3/BinarySearchTree.h
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. You may remove any code from these files that is unnecessary.
Write Proj3.cpp and any supporting files required to process the command file.
Implement new BinarySearchTree methods required to process commands contained in the command file.
Implement any non-member, non-friend BST functions necessary to process commands in the command file.
Implement any necessary BST iterators necessary to support your new BST methods or non-member functions.
Answer the questions posed in 341-Spring07-proj3_questions.txt. Copy the file

/afs/umbc.edu/users/f/r/frey/pub/CMSC341/Proj3/341-spring07-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.

Special project requirements and restrictions

Each command in the command file must be echoed to cout. See the sample output below.
You cannot add a NAME data member to the BinarySearchTree class, nor are "parallel" structures (one for the names and another for the actual BSTs) allowed.
You cannot add a data member to the BinarySearchTree class to store the tree's height.
You cannot add a data member to the BinarySearchTree class to store the number of leaves in the tree.
You cannot add a data member to the BinarySearchTree class to store the number of nodes in the tree.
The functions for intersection and union must be non-member, non-friend functions.
Only the author's BST code is provided. If your program requires other data structures (e.g, queue, stack, list) you must use those provided in the STL.

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 and abort your program 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. Line which begin with '#' are comments and should also be ignored. Otherwise, you can assume that any line containing a command is syntactically well-formed. We make this assumption so you can use the stream extraction operator to read your file and so you don't have to spend lots of time making the command file parser bullet proof.

All of the commands below refer to trees by names that are strings. When creating a tree (the TREE command), you must ensure that a tree with the same name does not already exist. If a tree with the specified name already exists, 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.

Any command may be duplicated and the commands may appear in any order.

The command file format follows:

TREE <NAME> <N> <V₁ V₂ ... V_N > - This command asks you to create a binary search tree of integers 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 (V₁ V₂ ... V_N). Read each value and insert it into the tree in the order in which it was read.
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 must be implemented as a public BST method that takes another BST 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 and be implemented as a public BST method.
FULL <NAME> - Print a message indicating whether the tree named NAME is a full binary tree. Your solution must involve recursion and be implemented as a new public BST method.
HEIGHT <NAME> - Print a message indicating the height of the tree named NAME. Your solution must involve recursion and be implemented as a public BST method. Hint: By convention, and for ease of coding, the height of an empty tree is defined as -1.
LEAVES <NAME> - Print a message indicating the number of leaves in the tree named NAME. Your solution must involve recursion and be implemented as a public BST method.
NODES <NAME> - Print a message indicating the number of nodes in the tree named NAME. Your solution must involve recursion and be implemented as a public BST method.
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 MAY NOT implemented as a BST method. Rather, you must write a non-member non-friend function whose parameters are the BSTs to be unioned. 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 MAY NOT be implemented as a BST method. Rather, you must write a non-member non-friend function whose parameters are the BSTs to be intersected. Neither of the trees that are intersected should be modified.
PRINT <NAME> - Print the number of nodes and the contents of the tree named NAME using an level-order traversal. This command should be implemented as a public BST method. Each level of the BST must be output on a separate line with an appropriate label.
5 Points Extra Credit
COMPLETE <NAME> - Print a message indicating whether the tree named NAME is a complete tree. Your solution must involve recursion and be implemented as a new public BST method.
If you choose not to implement COMPLETE, your project should print an appropriate message when COMPLETE is found in the command file.

Sample Output

The following input file:

TREE amy 3 20 10 30
TREE bob 3 10 5 15
PERFECT amy
PRINT bob
PERFECT bob
LEAVES bob
HEIGHT bob
UNION carl amy bob
PRINT carl
INTERSECTION dave amy bob
PRINT dave

creates the following output. Note that different methods of implementing UNION and INTERSECTION may result in trees with different shapes than those shown below.

Command: TREE amy 3 20 10 30
Tree "amy" created with 3 nodes

Command: TREE bob 3 10 5 15
Tree "bob" created with 3 nodes

Command: PERFECT amy
Tree "amy" is perfect

Command: PRINT bob
Tree "bob" has 3 nodes
Level 0: 10
Level 1: 5 15

Command: PERFECT bob
Tree "bob" is perfect

Command: LEAVES bob
Tree "bob" has 2 leaves

Command: HEIGHT bob
Tree "bob" has height 1

Command: UNION carl amy bob
Tree "carl" created with 5 nodes

Command: PRINT carl
Tree "carl" has 5 nodes
Level 0: 20
Level 1: 10 30
Level 2: 5 15

Command: INTERSECTION dave amy  bob
Tree "dave" created with 1 nodes

Command: PRINT dave
Tree "dave" has 1 nodes
Level 0: 10

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/f/r/frey/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 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) and checkfile.dat is in your local directory.

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-spring07-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.