Exercise 1:

Implement the BinarySearchTree ADT in bst.cpp exactly as shown below.

// bst.cpp

#ifndef BST_H

#define BST_H

#include

#include

#include

using namespace std;

template

class BinarySearchTree

{

public:

BinarySearchTree( ) : root(nullptr)

{ }

~BinarySearchTree( )

{

makeEmpty();

}

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 printBST( ) const

{

if( isEmpty( ) )

cout << "Empty tree" << endl;

else

printBST( 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 printBST( BinaryNode* t) const

{

if( t != nullptr )

{

printBST( t->left );

cout << t->element << " - ";

printBST( 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

Exercise 2:

Program your own file lab08.cpp in which your main() function will test the new data structure. The main() function,

Declares an instance of BinarySearchTree (short: BST) suitable to hold integer values.

Prompts user to enter a random sequence of integer values, inserts these values into the binary search tree (the entered

values should NOT be in sorted order).

Calls the printBST() member function to print out the values of the binary search tree.

Prompts user to enter a random sequence of integer values, remove these values from your binary search tree. Print

out the reduced binary search tree.

Declares an instance of BinarySearchTree suitable to hold strings.

Prompts user to enter a random sequence of string,

inserts these strings into the binary search tree (the entered values

should NOT be in sorted order).

Calls the printBST() member function to print out the string in the binary search tree.

Exercise 3:

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.

Add the following member function in your BinarySearchTree class template.

public:

void printRange(const C & k1, const C & k2) const

{

printRange(root, k1, k2);

}

private:

void printRange(BinaryNode* t, const C & k1, const C & k2) const

{

// add your code

}

Go back to your program lab08.cpp, prompt user to enter k1 and k2 (k1 < k2) and call printRange .

Compile and

run your program, and see what you get.

The expected result:

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

print the values:

1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 13 - 15 - 18 - 19 - 20 - 22 - 30 -

remove the values (stop when entering 0):

1 11 2 12 3 13 0

print the values:

4 - 5 - 6 - 7 - 8 - 9 - 10 - 15 - 18 - 19 - 20 - 22 - 30 -

Please enter the range: 5 10

Print the element between the range:

5 - 6 - 7 - 8 - 9 - 10 -

insert the strings (stop when entering "exit"):

hh ll aa ss ii uu ee bb cc pp qq mm zz xx exit

print the values:

aa - bb - cc - ee - hh - ii - ll - mm - pp - qq - ss - xx - zz -