Below is the provided "Binarysearchtreelab7.h"

-------------------------------------------------------------------------------------------------------------------------------

#ifndef BINARY_SEARCH_TREE_H #define BINARY_SEARCH_TREE_H //#include "dsexceptions.h" #include  #include  using namespace std; template  class BinarySearchTree { private: struct BinaryNode { C element; BinaryNode *left; BinaryNode *right; BinaryNode *parent; BinaryNode( const C & theElement, BinaryNode *lt, BinaryNode *rt, BinaryNode* par) : element{ theElement }, left{ lt }, right{ rt }, parent{par} { } BinaryNode( C && theElement, BinaryNode *lt, BinaryNode *rt, BinaryNode * par) : element{ std::move( theElement ) }, left{ lt }, right{ rt },parent{par} { } }; public: class iterator { public: iterator () : current(nullptr) {} iterator (BinaryNode * t) :current(t) {} C & operator *() const { return current->element; } //prefix iterator & operator ++() { // fill in return *this; } //postfix iterator & operator ++(int) { iterator old(*this); ++(*this); return old; } bool operator ==(iterator other) const { return current == other.current; } bool operator != (iterator other) const { return current != other.current; } protected: BinaryNode * current; // various internal functions ... // see Step 4 of Lab7 }; public: BinarySearchTree( ) : root{ nullptr } { } BinarySearchTree( const BinarySearchTree & rhs ) : root{ nullptr } { root = clone( rhs.root ); } BinarySearchTree( BinarySearchTree && rhs ) : root{ rhs.root } { rhs.root = nullptr; } ~BinarySearchTree( ) { makeEmpty( ); } BinarySearchTree & operator=( const BinarySearchTree & rhs ) { BinarySearchTree copy = rhs; std::swap( *this, copy ); return *this; } BinarySearchTree & operator=( BinarySearchTree && rhs ) { std::swap( root, rhs.root ); return *this; } const C & findMin( ) const { assert(!isEmpty()); return findMin( root )->element; } const C & findMax( ) const { assert(!isEmpty()); return findMax( root )->element; } bool contains( const C & x ) const { return contains( x, root ); } bool isEmpty( ) const { return root == nullptr; } void printTree( ostream & out = cout ) const { if( isEmpty( ) ) out left != 0) t = t->left; iterator beg(t); return beg; } iterator end() const { iterator end(0); return end; } void parent_check() { parent_check(root); } private: BinaryNode *root; /** * Internal method to insert into a subtree. * x is the item to insert. * t is the node that roots the subtree. * Set the new root of the subtree. */ void insert( const C & x, BinaryNode * & t, BinaryNode * & par ) { if( t == nullptr ) t = new BinaryNode{ x, nullptr, nullptr, par }; else if( x element ) insert( x, t->left, t ); else if( t->element right, t ); else ; // Duplicate; do nothing } /** * Internal method to insert into a subtree. * x is the item to insert. * t is the node that roots the subtree. * Set the new root of the subtree. */ void insert( C && x, BinaryNode * & t, BinaryNode * & par ) { if( t == nullptr ) t = new BinaryNode{ std::move( x ), nullptr, nullptr, par }; else if( x element ) insert( std::move( x ), t->left, t ); else if( t->element right, t ); else ; // Duplicate; do nothing } /** * Internal method to remove from a subtree. * x is the item to remove. * t is the node that roots the subtree. * Set the new root of the subtree. */ void remove( const C & x, BinaryNode * & t ) { if( t == nullptr ) return; // Item not found; do nothing if( x element ) remove( x, t->left ); else if( t->element right ); else if( t->left != nullptr && t->right != nullptr ) // Two children { t->element = findMin( t->right )->element; remove( t->element, t->right ); } else { BinaryNode *oldNode = t; if (t->left != nullptr) { t->left->parent = t->parent; t = t->left; } else { if (t->right != 0) t->right->parent = t->parent; t = t->right; } delete oldNode; } } void parent_check(BinaryNode *t) { if(t == nullptr) return; if (t->parent == nullptr) cout element element parent->element left); parent_check(t->right); return; } /** * Internal method to find the smallest item in a subtree t. * Return node containing the smallest item. */ BinaryNode * findMin( BinaryNode *t ) const { if( t == nullptr ) return nullptr; if( t->left == nullptr ) return t; return findMin( t->left ); } /** * Internal method to find the largest item in a subtree t. * Return node containing the largest item. */ BinaryNode * findMax( BinaryNode *t ) const { if( t != nullptr ) while( t->right != nullptr ) t = t->right; return t; } /** * Internal method to test if an item is in a subtree. * x is item to search for. * t is the node that roots the subtree. */ bool contains( const C & x, BinaryNode *t ) const { if( t == nullptr ) return false; else if( x element ) return contains( x, t->left ); else if( t->element right ); else return true; // Match } void makeEmpty( BinaryNode * & t ) { if( t != nullptr ) { makeEmpty( t->left ); makeEmpty( t->right ); delete t; } t = nullptr; } void printTree( BinaryNode *t, ostream & out ) const { if( t != nullptr ) { printTree( t->left, out ); out element right, out ); } } void printInternal(BinaryNode* t, int offset) { if (t == nullptr) return; for(int i = 1; i element left, offset + 1); printInternal(t->right, offset + 1); } BinaryNode * clone( BinaryNode *t ) const { if( t == nullptr ) return nullptr; else return new BinaryNode{ t->element, clone( t->left ), clone( t->right ), clone(t->parent)}; } }; #endif

In this lab we will enhance our BinarySearchTree implementation with additional functionalities that are necessary in order to build the Set and Map data structures on top of binary search trees. Because these enhancements are fairly involved, this lab will be run in a more instruction-based "follow-the-leader" type manner. Follow the instructions and make sure you keep up. If you find that the pace is too fast, please speak up and we slow down .. Step 1: Obtain a fresh copy of the BinarySearchTree implementation with BinarySearchTreeLab7.h from the instructor's directory. Step 2: Make additions to the code that will have each BinaryNode (node that contains the data values) have one addition pointer to its "parent" node. With this additional link, we will be able to traverse the tree in both directions: (1) down to the leaf nodes, and (2) upward to the root node. Follow the leader in making all additions to the code. Step 3: Test your new version of class BinarySearchTree by making sure that building a binary search tree, and removing elements are still working. Step 4: Insert into class Bina rySearchTree under public:" the following iterator class: struct BinaryNode; class iterator public: iterator current (0) iterator (BinaryNode t)current (t) T& operator const return current->element; iterator & operator++ () // MUCH TO BE FILLED IN.. return this; In this lab we will enhance our BinarySearchTree implementation with additional functionalities that are necessary in order to build the Set and Map data structures on top of binary search trees. Because these enhancements are fairly involved, this lab will be run in a more instruction-based "follow-the-leader" type manner. Follow the instructions and make sure you keep up. If you find that the pace is too fast, please speak up and we slow down .. Step 1: Obtain a fresh copy of the BinarySearchTree implementation with BinarySearchTreeLab7.h from the instructor's directory. Step 2: Make additions to the code that will have each BinaryNode (node that contains the data values) have one addition pointer to its "parent" node. With this additional link, we will be able to traverse the tree in both directions: (1) down to the leaf nodes, and (2) upward to the root node. Follow the leader in making all additions to the code. Step 3: Test your new version of class BinarySearchTree by making sure that building a binary search tree, and removing elements are still working. Step 4: Insert into class Bina rySearchTree under public:" the following iterator class: struct BinaryNode; class iterator public: iterator current (0) iterator (BinaryNode t)current (t) T& operator const return current->element; iterator & operator++ () // MUCH TO BE FILLED IN.. return this