CIS-3050 Algorithms and Data Structures

Assignment 4

Due:  Wednesday, Nov. 3

This assignment is to write a basic binary tree implementation.

 Create a Node class  (it is fine to do this all in Node.h) that supports the following methods:

This Node class is "smart" in that it does much of the work for the binary tree.   Specifically, add() will need to determine if the particular value needs to be added to the left or right of this particular node, and recursively call add on the appropriate Node (left or right).   If the value is equal to the value on the Node, add() should just silently return -- which gives this Tree Set-like functionality

print() is an in order traversal of the Tree, printing each element.

Create a Tree class that supports the following methods:
The Tree class is pretty much a wrapper around Node.  add() and print() both need to handle cases where the Tree's root doesn't have children, but otherwise, it just calls the appropriate function on Node for the appropriate

Write a main() that adequately tests your Tree functionality.

For extra credit, you may also implement both pre and post order print functions on both Node and Tree:

void printPre();          // performs an preorder print of the tree
void printPost();          // performs an postorder print of the tree

Be sure to update your test to demonstrate this functionality as well.

To be turned in: 
    1. Your  implementation of the Tree and Node classes.  This will consist of Tree.h and Node.h
    2. A program (C++ main) that fully tests the  functionality.  Be sure to test all the public functions. 

As needed, I can be reached via email, AIM or in my office on the 2nd floor of the 700 building.  See my schedule page for my official office hours.    If you do need help, including your source code files in any email to me can be helpful and save time.

Good Luck and Good Coding!