#include "BinaryTree.h" template class BinarySearchTree : public BinaryTree { public: /** * Function to insert an element into the BST * Input Parameter: the element to insert */ void insert(const ItemType& element) { //if the tree is empty, use createRoot if (BinaryTree::empty()) BinaryTree::createRoot(element); else { //need to find the correct spot typename BinaryTree::Iterator current = BinaryTree::root(); bool done = false; while (!done) { if (element < *current) { //value is to the left if (current.hasLeftChild()) current = current.left(); else done = true; } else { //element is to the right if (current.hasRightChild()) current = current.right(); else done = true; } } //end while loop if (element < *current) BinaryTree::insertAsLeftChild(element, current); else BinaryTree::insertAsRightChild(element, current); } //end of else } //end of insert /** * Function to find if an element is in the tree * Input Parameter: the element to search for * Return value: an iterator to the node if it is present, or a null iterator if not */ typename BinaryTree::Iterator find(const ItemType& value) { typename BinaryTree::Iterator current; current = BinaryTree::root(); while (current != BinaryTree::end()) { if (*current == value) return current; if (*current < value) current = current.right(); else current = current.left(); } return current; } /** * Function to remove an element from the tree */ void remove(const ItemType& element) { //hw } }; // end BinarySearchTree.h