Assigned | Monday, March 26, 2007 |
Due | Sunday, April 8, 2007 at 11:59pm |
Updates | 26 March 2007
|
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:
/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.
/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
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.
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:
5 Points Extra Credit
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 davecreates 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
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.
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.
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.