Transitions Project 4: Lets Turn your
list into a Tree
Due Thursday March 25th at 11:59pm
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.
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
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.
Make sure to include a readme.txt
It should include
- Your name
- your description on how you implemented the lab - particularly how your print works
- your compile/link commands (whatever I need to do to make your project.)
- Anything that is left undone.
zip up your folder with all code and the readme as before