Purpose
This project will give you experience with Binary Search Trees. You will build upon this project with the next project, so be sure you document your code well and understand well how it works.
Implement the two classes defined in the following UM L diagrams.
-+ root: Node-
BinarySearchTree
.data'int
-heighl.lnl
Node
-BlnarySearcnTree()
-•BinaryS •• rcnrr •• O
+Insert(data:ilt): void
•lnsertHefpet(cursor.Node', data:int): Node'
+Search(data:int): Nodes
•SearehHelper(eursor:Node', data:lnl~ Node'
+Remove(dala:int): void
•RemoveHelper(eursor.NOde', data.inl). NOde'
+lnorderTraversal(): void
•lnorderHelper(eursor:NOde'): void
-Pnntt): void
•PrlntHelper(O"Setstd::string&', cursor.NOde'): voto
-Size(): int
•SlzeHelper(cursor.Node'): inl
+leftChilct Node"
-righIChHd: Node'
•neededForunuest Observer
-Node(data:inl, lenChil<l:Node', rightChild:NOde')
.. NOd.O
-ISleatO : boot
-UpdateHeightO : void
You need to implement these two UML diagrams in:
Node.h Node.cpp BinarySearchTree.h BinarySearchTree.cpp
Recursion
The following functions in BinarySearchTree MUST be implemented using recursion (their recursive 'helper" functions are specified in the
UML diagram):
Insert Search Remove
InorderTraveral
Print
Size
Unit Testing
ZyLabs will be auto-grading this project
The Node and BinarySearchTree classes must be implemented EXACTLYas shown in the above UML diagrams. Main.cpp MUST include "Ooserver.h' and 'RecursionCounter.h' near the beginning of the file.
Main.cpp MUST define the following four static variables for these two classes as shown below:
include"BinarySearchTree.h" include"Observer.h" include"RecursionCounter.h"
II needed for Unit Testing. DO NOT REMOVE intObserver::numConstructions = 0; intObserver::numDestructions = 0; intRecursionCounter::currentDepth = 0; intRecursionCounter::maxDepth = 0;
int mainO
{
Also, to assist the Unit Testing portion of ZyLabs, the Node class MUST have a private variable of type "Observer'. This means that Node.h must #include "Observer.h' at the top of the file. i.e.:
include"Observer.h"
classNode
{
public:
1/ your code goes here
private:
Observer neededForUnitTest; /1 do not remove
};
To allow the Unit Test to verify that recursion is properly being used, one local variable of type RecursionCounter needs to be declared at the beginning of EACH** Recursive 'Helper" function**. For example:
intBinarySearchTree::SizeHelper(Node * cursor)
{
RecursionCounter neededForUnitTest; /1 MUST BE HERE
1/ base case
Main Driver
In Main.cpp implement the function mainO which creates a BinarySearchTree object and performs the following:
1. Insert the following data into your tree:
2. 21,26,30,9,4,14,28,18,1 5,10,2,3,7
3. Perform an In-order traversal of the tree
4. Print the tree
5. Remove the following data from the tree
6. 21,9,4,18,15,7
7. Print the tree
8. Perform an In-order traversal of the tree
The output should look like:
Image missing
