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

At the end of Lab7, everyone should have left an enhanced version of the binary search tree implementation in a file BinarySearchTreeLab7.h. If you do not have your own file with code that compiles, you may download a copy from the HW3 area on Blackboard. For this homework, you will be filling the missing code into the following member functions of class iterator (within class BinarySearchTree): bool is_root (BinaryNode* t) returns true when t is a pointer to the BinaryNode that is the "root"; the root is the only BinaryNode that has nullptr as its parent; bool is_left_child (BinaryNode t) returns true when t is a pointer to a BinaryNode that is the left child of its parent; test whether t's parent's left child is the same ast; bool is_right_child (BinaryNode t) analogous to is_left_child; BinaryNode leftmost (BinaryNode t) starting at t, follow the left children and return a pointer to the deepest leftmost child; BinaryNode follow_parents_until_leftchild (BinaryNode * t) starting at t, follow the parent links upwards until a BinaryNode is reached which is a left child; return a pointer to this left child's parent; . Implement the bodies of these functions so that they behave as described (3 points for each function) At the end of Lab7, everyone should have left an enhanced version of the binary search tree implementation in a file BinarySearchTreeLab7.h. If you do not have your own file with code that compiles, you may download a copy from the HW3 area on Blackboard. For this homework, you will be filling the missing code into the following member functions of class iterator (within class BinarySearchTree): bool is_root (BinaryNode* t) returns true when t is a pointer to the BinaryNode that is the "root"; the root is the only BinaryNode that has nullptr as its parent; bool is_left_child (BinaryNode t) returns true when t is a pointer to a BinaryNode that is the left child of its parent; test whether t's parent's left child is the same ast; bool is_right_child (BinaryNode t) analogous to is_left_child; BinaryNode leftmost (BinaryNode t) starting at t, follow the left children and return a pointer to the deepest leftmost child; BinaryNode follow_parents_until_leftchild (BinaryNode * t) starting at t, follow the parent links upwards until a BinaryNode is reached which is a left child; return a pointer to this left child's parent; . Implement the bodies of these functions so that they behave as described (3 points for each function)