In this assignment you will implement a generic binary tree and a generic binary search tree where the data is stored in a STL vector.

Steps

1. Inherit a class "binaryTree" from binaryTreeInterface.h and overload all the functions. When adding and removing items, the order doesn't matter at all. You can add anywhere in the tree and move items around when removing an item if you need to. 30%
2. Inherit a class "binarySearchTree" from "binaryTree" of the previous step or the binaryTreeInterface.h and overload at least the addNode, remove_one, and remove_all functions. Remember that in a binary search tree, in-order traversal of the tree visits the items in the increasing order. Overloading the addNode is worth 30% of the mark, overloading remove_one is worth another 30% and overloading remove_all is worth 10% of the mark.

How to test?

You can use the binary tree tester file and binary search tree tester file to check your output. You need a compiler of C++11 or later to compile these tester files. In the binary tree, the order doesn't matter at all. In the bianrySearchTree however, you must check that in-order traverse is giving you all the items in a sorted order. Also, make sure the frequencies of the items in both trees are correct.

Here is the result I get from my implementation. Remember your pre-order and post-order traversals don't have to match with mine exactly. In the case of binary search tree your in-order traverse must match with mine but in the case of binary tree it doesn't have to.

g++ --std=c++0x -o test_binarySearchTree.o test_binarySearchTree.cpp 
./test_binarySearchTree.o 
pre-order: 10 4 12 11 102 83 51 23 23 51 51 91 
post-order: 4 11 23 23 51 51 51 91 83 102 12 10 
in-order: 4 10 11 12 23 23 51 51 51 83 91 102 
height:6
removing 10, 5, 12, 83, and all instances of 51 ...
pre-order: 11 4 23 102 91 23 
post-order: 4 23 91 102 23 11 
in-order: 4 11 23 23 91 102 
height:4

Now working with strings:

pre-order: 10 12 102 11 83 51 23 4 23 51 51 91 
post-order: 11 102 23 4 23 51 51 51 91 83 12 10 
in-order: 10 102 11 12 23 23 4 51 51 51 83 91 
height:6
removing "10", "5", "12", "83", and all instances of "51" ...
pre-order: 102 23 11 91 4 23 
post-order: 11 23 4 91 23 102 
in-order: 102 11 23 23 4 91 
height:4

g++ --std=c++0x -o test_binaryTree.o test_binaryTree.cpp 
./test_binaryTree.o 
pre-order: 10 12 11 4 91 83 51 23 102 51 51 23 
post-order: 4 91 11 51 23 83 12 51 51 23 102 10 
in-order: 4 11 91 12 51 83 23 10 51 51 102 23 
height:3
removing 10, 5, 12, 83, and all instances of 51 ...
pre-order: 91 23 11 4 102 23 
post-order: 11 4 23 23 102 91 
in-order: 11 23 4 91 23 102 
height:2

 Now working with strings:

pre-order: 10 12 11 4 91 83 51 23 102 51 51 23 
post-order: 4 91 11 51 23 83 12 51 51 23 102 10 
in-order: 4 11 91 12 51 83 23 10 51 51 102 23 
height:3
removing "10", "5", "12", "83", and all instances of "51" ...
pre-order: 91 23 11 4 102 23 
post-order: 11 4 23 23 102 91 
in-order: 11 23 4 91 23 102 
height:2

Caution

Your implementation must be

• generic
• vector based
• inheritd from binaryTreeInterface.h.

Failing to comply with these restrictions will result in a zero.

What to submit?

1. binarySearchTree.h
2. binaryTree.h

Where to submit?

In CourSys under CMPT 225 Assignment4 activity.

Final Note

While it is OK for you to discuss the high-level idea of how to tackle each of these steps among yourselves, I encourage you to try coming up with the idea yourself. Remember, one of the most important goals of the course is to build your problem-solving skills.

---