In C++ I need the printRange function, and the main.cpp program. Thanks.

(Binary search tree) Write a function printRange that takes as input a binary search tree t and two keys, k1 and k2, which are ordered so that k1 < k2, and print all elements x in the tree such that k1 <= x <= k2.

You can add this function in BinarySearchTree.h (click the link) that we used in the lecture and lab 7.

public:

void printRange(int k1, int k2)

{ printRange(root,k1, k2);

}

private:

void printRange(BinaryNode* t, int k1, int k2)

{

// add your code

}

Here are the sample runs:

insert the values (stop when entering 0): 10 5 20 3 22 6 18 7 9 13 15 4 2 1 19 30 8 0

enter the range of values: 8 18

print the values: 8, 9, 10, 13, 15, 18,

Here is BinarySearchTree.h

#ifndef BINARY_SEARCH_TREE_H #define BINARY_SEARCH_TREE_H #include  #include  using namespace std; template  class BinarySearchTree { public: BinarySearchTree( ) : root{ nullptr } { } ~BinarySearchTree( ) { makeEmpty(); } bool isEmpty( ) const { return root == nullptr; } 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 ); } void printTree( ) const { if( isEmpty( ) ) cout << "Empty tree" << endl; else printTree( root ); } void makeEmpty( ) { makeEmpty( root ); } void insert( const C & x ) { insert( x, root ); } void remove( const C & x ) { remove( x, root ); } private: struct BinaryNode { C element; BinaryNode* left; BinaryNode* right; BinaryNode( const C & theElement, BinaryNode* lt, BinaryNode* rt ) : element{ theElement }, left{ lt }, right{ rt } { } }; BinaryNode* root; // 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 < t->element ) return contains( x, t->left ); else if( t->element < x ) return contains( x, t->right ); else return true; // Match } void printTree( BinaryNode* t) const { if( t != nullptr ) { printTree( t->left); cout << t->element << " - "; printTree( t->right); } } void makeEmpty( BinaryNode* & t ) { if( t != nullptr ) { makeEmpty( t->left ); makeEmpty( t->right ); delete t; } t = nullptr; } // 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 ) { if( t == nullptr ) t = new BinaryNode{ x, nullptr, nullptr }; else if( x < t->element ) insert( x, t->left ); else if( t->element < x ) insert( x, t->right ); 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 < t->element ) remove( x, t->left ); else if( t->element < x ) remove( x, t->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 = t->right; else t = t->left; delete oldNode; } } }; #endif