Transitions Project 4: Lets Turn your list into a Tree


Due Thursday March 25th at 11:59pm

Summary

I have been told that several of you had problems with project 2 (the linked list project with pointers and memory management) so In this project you will repeat project 2 except you will use a binary tree rather than a linked list.

Details:

Create a binary using a node class which uses pointers to other node objects to keep track of the next node. Allow adding nodes to the leaf of the tree.
The biggest difference between a linked list node and a simple tree node is that the linked list has one next pointer to a node while a binary tree has two pointers to nodes - a left and a right.

Your node should have at least a name and the two pointers. Your node must be a class and not a struct.

Once again you must allow the user to add to the tree, and remove an item from the tree based on the name of the object.

So your binary tree needs to support three major operations (Along with constructors and any other operators needed)

Add: should take a node, and place it at the leaf of the tree in alphabetical order. If the new node has a name that is alphabetically before the item on the left of the three, it needs to go on the left of that node. (see diagram on board during class)

Remove: should remove the node with that name (don't worry about duplicates) without corrupting memory or losing any of the tree. For simplicity lets always replace the node being removed with its right hand child. Insert the left hand child (and thus all remaining parts of the tree) into the first free left hand spot in the resulting new branch of the tree.

Print: Print the tree out. Your choice of the order, just be sure to mention it in your readme file.

You do not need to rebalance the tree if it gets unbalanced after inserts and deletes.

Once again don't leak memory!

Refer to my solution to the list lab and see me early if you are having problems.

Readme:

Make sure to include a readme.txt
It should include

Submission:

zip up your folder with all code and the readme as before