Description
P3 exercises your understanding of Binary Search Trees (multiply linked lists), Recursion
and Simulation of recursion with a stack data structure in C++
Create a (partial) BST class and a driver program to test it. The tree node will store
integers as the data and key field. Note that you will need to guarantee there are no
duplicates in your insert function (refuse to insert a duplicate key).
Because this is a structure with dynamic memory in C++, you must include the memory
management methods.
Call your files “tree.h”, “tree.cpp” and “p3.cpp”. Submit your project by typing the
following command from the prompt in the directory where the files are located:
/home/fac/sreeder/submit/cpsc2430/p3_runme
Public methods to include:
Constructor
Copy Constructor
Overloaded Assignment Operator
Destructor
Insert value (do not add duplicate values)
Find key – returns bool indicating if value is present in tree
Find min key – returns min key value
Find max key – returns max key value
Find height – returns integer
Pre-Order Traversal done recursively (print key values to screen)
In-Order Traversal done iteratively (print key values to screen)
(may use STL Stack for this)
Remove key
There may be additional private helper methods as needed.
Your driver should add a minimum of 20 random values to the tree, then arbitrarily
insert and remove values. Test all the public methods of your class in the driver, printing
the results to the screen.
