CS2141 Program Two

Due: Friday, 12 February 2010, at 11:59pm

Binary trees are, along with linked lists, among the most common data structures in modern Computer Science, and have a part in the implementation of a wide varieties of other structures. For all their importance, though, binary trees are easy to understand, easy to write, and provide an excellent starting point for dealing with classes and heap-based (dynamic) memory management.

For this assignment, you will be creating a simple binary tree class, and using it to store and retrieve user input.

Goals

The goals of this assignment are:

To gain some more experience with C++, especially interacting with the user
To practice building a simple class in C++
To work with pointers
To practice allocating and removing memory using the new and delete keywords.
To work with Makefiles

Problem Description

Your program will implement a simple binary tree, capable of storing a set of integers. A user will be able to issue simple commands which will cause a value to be added to the tree, the tree to be emptied, or the contents of the tree to be printed to the screen. There is also a command to exit your program.

Your goal is to receive these commands and execute them on your tree.

Input

Your program will receive a sequence of commands from cin, with the individual commands separated by whitespace. Here are the commands:

Command	Meaning
i int	Insert the number int into the tree. If it already exists, do not insert it a second time.
e	Empty the tree (delete all numbers within it)
p	Print out the contents of the tree. See Output, below, for details.
q	Quit the program. No other output should be generated.

Example input:

i 10 i 13 i 10
e p q

Ouput

Output should only be generated if/when you program received the command p. In that case, you should either print out the values in your tree using an in-order traversal, (if the list is non-empty), or print "empty" if there is nothing currently stored in the tree. There should be a single space between successive values.

Here are examples illustrating both cases (assume the list was empty when the first command was received):

Input	i 10 i 13 i 10 e p	Output	empty
Input	i 10 i 5 i 2 i 1 i 10 p	Output	1 2 5 10

Code Requirements

Binary Tree Class

Your code must include a class which implements the binary tree functionality. This class must, at the very least, implement methods for inserting individual nodes / values, emptying the list, and printing the contents of the tree. You will also need at least one constructor, and you must provide a destructor. Beyond those requirements, the details of the implementation are completely up to you.

Remember that any memory you allocate with new you must free with delete.

Makefile

You will provide a Makefile that we can use to compile and run your program. It needs to include rules for default (just compile the program), clean (delete .o files and the executable), and run (compile, if necessary, and run). The Makefile provided with the solution to Program 1 does everything yours needs to do, so go ahead and modify that to fit your needs.

Source Files and Headers

The main function must be implemented in one file (as was the case with HW1), the binary tree class must be defined separately, and should make use of separate header and implementation files. Other functions / classes (if needed) may be implemented in one or more source files. All source files (except the file with "main") must have their own header file. (The names of the files are not important since you will be providing a Makefile.)

Other Guidelines

No global variables. Global constants are okay though, but make sure they're declared const.
Any memory you allocate with new must be freed with delete before the program exits.
You may only use the functions and classes defined in iostream. Everything else must be your own creation.
Here is the grading scale for this program.
The Code Style Guidelines are in full effect for this assignment.

Hopefully Helpful Hints

Start Early! It's okay to finish early.
C++ switch statements are equivalent to those in Java, and will probably be very useful for figuring out the user commands.
If you need a refresher on Binary Trees, Wikipedia has a fairly informative article on the subject.
Make sure you comment your code! Proper documentation and formatting is an important part of your grade, and also makes it easier to reuse your code later on.
If you need help, you can ask your instructor.

Have fun, and remember that all the usual rules regarding cheating and cooperation are in full effect for this program.

This page last updated 24 January 2010