Please help me with implementing this binary search tree. Here is the code provi
ID: 3820056 • Letter: P
Question
Please help me with implementing this binary search tree.
Here is the code provide with the homework.
dsexceptions.h
#ifndef DS_EXCEPTIONS_H
#define DS_EXCEPTIONS_H
class UnderflowException { };
class IllegalArgumentException { };
class ArrayIndexOutOfBoundsException { };
class IteratorOutOfBoundsException { };
class IteratorMismatchException { };
class IteratorUninitializedException { };
#endif
BinarySearchTree.h
#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H
#include "dsexceptions.h"
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
// BinarySearchTree class
//
// CONSTRUCTION: zero parameter
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// void remove( x ) --> Remove x
// bool contains( x ) --> Return true if x is present
// Comparable findMin( ) --> Return smallest item
// Comparable findMax( ) --> Return largest item
// boolean isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// void printTree( ) --> Print tree in sorted order
// ******************ERRORS********************************
// Throws UnderflowException as warranted
template <typename Comparable>
class BinarySearchTree
{
public:
BinarySearchTree( ) : root{ nullptr }
{
}
/**
* Copy constructor
*/
BinarySearchTree( const BinarySearchTree & rhs ) : root{ nullptr }
{
root = clone( rhs.root );
}
/**
* Move constructor
*/
BinarySearchTree( BinarySearchTree && rhs ) : root{ rhs.root }
{
rhs.root = nullptr;
}
/**
* Destructor for the tree
*/
~BinarySearchTree( )
{
makeEmpty( );
}
/**
* Copy assignment
*/
BinarySearchTree & operator=( const BinarySearchTree & rhs )
{
BinarySearchTree copy = rhs;
std::swap( *this, copy );
return *this;
}
/**
* Move assignment
*/
BinarySearchTree & operator=( BinarySearchTree && rhs )
{
std::swap( root, rhs.root );
return *this;
}
/**
* Find the smallest item in the tree.
* Throw UnderflowException if empty.
*/
const Comparable & findMin( ) const
{
if( isEmpty( ) )
throw UnderflowException{ };
return findMin( root )->element;
}
/**
* Find the largest item in the tree.
* Throw UnderflowException if empty.
*/
const Comparable & findMax( ) const
{
if( isEmpty( ) )
throw UnderflowException{ };
return findMax( root )->element;
}
/**
* Returns true if x is found in the tree.
*/
bool contains( const Comparable & x ) const
{
return contains( x, root );
}
/**
* Test if the tree is logically empty.
* Return true if empty, false otherwise.
*/
bool isEmpty( ) const
{
return root == nullptr;
}
/**
* Print the tree contents in sorted order.
*/
void printTree( ostream & out = cout ) const
{
if( isEmpty( ) )
out << "Empty tree" << endl;
else
printTree( root, out );
}
/**
* Make the tree logically empty.
*/
void makeEmpty( )
{
makeEmpty( root );
}
/**
* Insert x into the tree; duplicates are ignored.
*/
void insert( const Comparable & x )
{
insert( x, root );
}
/**
* Insert x into the tree; duplicates are ignored.
*/
void insert( Comparable && x )
{
insert( std::move( x ), root );
}
/**
* Remove x from the tree. Nothing is done if x is not found.
*/
void remove( const Comparable & x )
{
remove( x, root );
}
// public:
/**
* Return tree walks of three types as a vector of elements in the tree
* 0 - preorder, 1 - inorder, 2 - postorder
*/
int treeWalk(int type, vector<Comparable> & t_walk){
if (root==NULL ){
cout << "Empty Tree." << endl;
return -1;
}
return treeWalk(root, type, t_walk);
}
/**
* Display the tree walks;
* does not work well for high trees.
*/
void displayTreeWalk(int type, ostream & out = cout ){
if (type<0 || type>2)
out << "Invalid type of tree walk" << endl;
switch(type){
case 0: out << "Preorder Tree Walk: ";
break;
case 1: out << "Inorder Tree Walk: ";
break;
case 2: out << "Postorder Tree Walk: ";
}
vector<Comparable> t_walk;
treeWalk(type, t_walk);
for(int i=0; i<t_walk.size(); i++)
cout << t_walk[i] << " ";
cout << endl;
}
private:
struct BinaryNode
{
Comparable element;
BinaryNode *left;
BinaryNode *right;
BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt )
: element{ theElement }, left{ lt }, right{ rt } { }
BinaryNode( Comparable && theElement, BinaryNode *lt, BinaryNode *rt )
: element{ std::move( theElement ) }, left{ lt }, right{ rt } { }
};
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 Comparable & 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 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( Comparable && x, BinaryNode * & t )
{
if( t == nullptr )
t = new BinaryNode{ std::move( x ), nullptr, nullptr };
else if( x < t->element )
insert( std::move( x ), t->left );
else if( t->element < x )
insert( std::move( 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 Comparable & 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;
t = ( t->left != nullptr ) ? t->left : t->right;
delete oldNode;
}
}
/**
* 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 Comparable & 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
}
/****** NONRECURSIVE VERSION*************************
bool contains( const Comparable & x, BinaryNode *t ) const
{
while( t != nullptr )
if( x < t->element )
t = t->left;
else if( t->element < x )
t = t->right;
else
return true; // Match
return false; // No match
}
*****************************************************/
/**
* Internal method to make subtree empty.
*/
void makeEmpty( BinaryNode * & t )
{
if( t != nullptr )
{
makeEmpty( t->left );
makeEmpty( t->right );
delete t;
}
t = nullptr;
}
/**
* Internal method to print a subtree rooted at t in sorted order.
*/
void printTree( BinaryNode *t, ostream & out ) const
{
if( t != nullptr )
{
printTree( t->left, out );
out << t->element << endl;
printTree( t->right, out );
}
}
/**
* Internal method to clone subtree.
*/
BinaryNode * clone( BinaryNode *t ) const
{
if( t == nullptr )
return nullptr;
else
return new BinaryNode{ t->element, clone( t->left ), clone( t->right ) };
}
/**
* Return tree walks of a subtree rooted at b_node of
* three types as a vector of elements in the tree
* 0 - preorder, 1 - inorder, 2 - postorder
*/
int treeWalk(BinaryNode *b_node, int type, vector<Comparable> & t_walk){
if (type<0 || type>2){
cout << "Invalid type of tree walk" << endl;
return -1;
}
if (b_node==NULL)
return 0;
int walk_done1, walk_done2;
switch(type){
case 0: t_walk.push_back(b_node->element);
walk_done1 = treeWalk(b_node->left, type, t_walk);
walk_done2 = treeWalk(b_node->right, type, t_walk);
break;
case 1: walk_done1 = treeWalk(b_node->left, type, t_walk);
t_walk.push_back(b_node->element);
walk_done2 = treeWalk(b_node->right, type, t_walk);
break;
case 2: walk_done1 = treeWalk(b_node->left, type, t_walk);
walk_done2 = treeWalk(b_node->right, type, t_walk);
t_walk.push_back(b_node->element);
break;
}
if (walk_done1 != 0 || walk_done2 != 0){
cout << "Something is wrong." << endl;
return -1;
}
return 0;
}
};
#endif
Here is the cpp code
TestBinarySearchTree.cpp
#include <iostream>
#include "BinarySearchTree.h"
using namespace std;
// Test program
int main( )
{
BinarySearchTree<int> t;
int NUMS = 400000;
const int GAP = 3711;
int i;
cout << "Checking... (no more output means success)" << endl;
for( i = GAP; i != 0; i = ( i + GAP ) % NUMS )
t.insert( i );
for( i = 1; i < NUMS; i+= 2 )
t.remove( i );
if( NUMS < 40 )
t.printTree( );
if( t.findMin( ) != 2 || t.findMax( ) != NUMS - 2 )
cout << "FindMin or FindMax error!" << endl;
for( i = 2; i < NUMS; i+=2 )
if( !t.contains( i ) )
cout << "Find error1!" << endl;
for( i = 1; i < NUMS; i+=2 )
{
if( t.contains( i ) )
cout << "Find error2!" << endl;
}
BinarySearchTree<int> t2;
t2 = t;
for( i = 2; i < NUMS; i+=2 )
if( !t2.contains( i ) )
cout << "Find error1!" << endl;
for( i = 1; i < NUMS; i+=2 )
{
if( t2.contains( i ) )
cout << "Find error2!" << endl;
}
// The following code randomly builds a BST and
// display all the three tree walks of the built tree.
BinarySearchTree<int> t3;
int numNodes = 10;
cout << "Building a random BST..." << endl;
srand(time(NULL));
for (i = 0; i< numNodes; i++)
t3.insert(rand()%1000);
cout << "Finished building a random BST." << endl;
cout << "Printing tree walks: " << endl;
t3.displayTreeWalk(0);
t3.displayTreeWalk(1);
t3.displayTreeWalk(2);
cout << "Finished testing" << endl;
return 0;
}
1. (50 pts) Basic Setup: Implement or adapt a BST class (preferred) or a package of data structures and functions that contains implementation of the following operations on BSTs: inorder/preorder/postorder walk, search, maximum, minimum, predecessor, successor, insert and delete You may implement those BST operations on your own or adapt any existing programs you can find that implement BSTs. n the latter case, you should indicate clearly where you obtain the source code and what significant modifications you made if any. You also need to include testing code to verify the correctness of your program. In particular, you should test all the operations on a randomly built BST. Attached is the source code for the BinarySearchTree class from the textbook that you can use I added several functions to output tree walks (treeWalk") as well as testing code for that. The attached program also includes code for randomly generate a BST For this project, each node in a BST should at least four fields: key called element in the provided code), p, left, and right, representing the key value, and parent, left, and right child nodes of the given node. In addition, key values of all nodes in a BST are assumed to be integers.Explanation / Answer
#ifndef DS_EXCEPTIONS_H
#define DS_EXCEPTIONS_H
class UnderflowException { };
class IllegalArgumentException { };
class ArrayIndexOutOfBoundsException { };
class IteratorOutOfBoundsException { };
class IteratorMismatchException { };
class IteratorUninitializedException { };
#endif
BinarySearchTree.h
#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H
#include "dsexceptions.h"
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
// BinarySearchTree class
//
// CONSTRUCTION: zero parameter
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// void remove( x ) --> Remove x
// bool contains( x ) --> Return true if x is present
// Comparable findMin( ) --> Return smallest item
// Comparable findMax( ) --> Return largest item
// boolean isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// void printTree( ) --> Print tree in sorted order
// ******************ERRORS********************************
// Throws UnderflowException as warranted
template <typename Comparable>
class BinarySearchTree
{
public:
BinarySearchTree( ) : root{ nullptr }
{
}
/**
* Copy constructor
*/
BinarySearchTree( const BinarySearchTree & rhs ) : root{ nullptr }
{
root = clone( rhs.root );
}
/**
* Move constructor
*/
BinarySearchTree( BinarySearchTree && rhs ) : root{ rhs.root }
{
rhs.root = nullptr;
}
/**
* Destructor for the tree
*/
~BinarySearchTree( )
{
makeEmpty( );
}
/**
* Copy assignment
*/
BinarySearchTree & operator=( const BinarySearchTree & rhs )
{
BinarySearchTree copy = rhs;
std::swap( *this, copy );
return *this;
}
/**
* Move assignment
*/
BinarySearchTree & operator=( BinarySearchTree && rhs )
{
std::swap( root, rhs.root );
return *this;
}
/**
* Find the smallest item in the tree.
* Throw UnderflowException if empty.
*/
const Comparable & findMin( ) const
{
if( isEmpty( ) )
throw UnderflowException{ };
return findMin( root )->element;
}
/**
* Find the largest item in the tree.
* Throw UnderflowException if empty.
*/
const Comparable & findMax( ) const
{
if( isEmpty( ) )
throw UnderflowException{ };
return findMax( root )->element;
}
/**
* Returns true if x is found in the tree.
*/
bool contains( const Comparable & x ) const
{
return contains( x, root );
}
/**
* Test if the tree is logically empty.
* Return true if empty, false otherwise.
*/
bool isEmpty( ) const
{
return root == nullptr;
}
/**
* Print the tree contents in sorted order.
*/
void printTree( ostream & out = cout ) const
{
if( isEmpty( ) )
out << "Empty tree" << endl;
else
printTree( root, out );
}
/**
* Make the tree logically empty.
*/
void makeEmpty( )
{
makeEmpty( root );
}
/**
* Insert x into the tree; duplicates are ignored.
*/
void insert( const Comparable & x )
{
insert( x, root );
}
/**
* Insert x into the tree; duplicates are ignored.
*/
void insert( Comparable && x )
{
insert( std::move( x ), root );
}
/**
* Remove x from the tree. Nothing is done if x is not found.
*/
void remove( const Comparable & x )
{
remove( x, root );
}
// public:
/**
* Return tree walks of three types as a vector of elements in the tree
* 0 - preorder, 1 - inorder, 2 - postorder
*/
int treeWalk(int type, vector<Comparable> & t_walk){
if (root==NULL ){
cout << "Empty Tree." << endl;
return -1;
}
return treeWalk(root, type, t_walk);
}
/**
* Display the tree walks;
* does not work well for high trees.
*/
void displayTreeWalk(int type, ostream & out = cout ){
if (type<0 || type>2)
out << "Invalid type of tree walk" << endl;
switch(type){
case 0: out << "Preorder Tree Walk: ";
break;
case 1: out << "Inorder Tree Walk: ";
break;
case 2: out << "Postorder Tree Walk: ";
}
vector<Comparable> t_walk;
treeWalk(type, t_walk);
for(int i=0; i<t_walk.size(); i++)
cout << t_walk[i] << " ";
cout << endl;
}
private:
struct BinaryNode
{
Comparable element;
BinaryNode *left;
BinaryNode *right;
BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt )
: element{ theElement }, left{ lt }, right{ rt } { }
BinaryNode( Comparable && theElement, BinaryNode *lt, BinaryNode *rt )
: element{ std::move( theElement ) }, left{ lt }, right{ rt } { }
};
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 Comparable & 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 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( Comparable && x, BinaryNode * & t )
{
if( t == nullptr )
t = new BinaryNode{ std::move( x ), nullptr, nullptr };
else if( x < t->element )
insert( std::move( x ), t->left );
else if( t->element < x )
insert( std::move( 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 Comparable & 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;
t = ( t->left != nullptr ) ? t->left : t->right;
delete oldNode;
}
}
/**
* 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 Comparable & 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
}
/****** NONRECURSIVE VERSION*************************
bool contains( const Comparable & x, BinaryNode *t ) const
{
while( t != nullptr )
if( x < t->element )
t = t->left;
else if( t->element < x )
t = t->right;
else
return true; // Match
return false; // No match
}
*****************************************************/
/**
* Internal method to make subtree empty.
*/
void makeEmpty( BinaryNode * & t )
{
if( t != nullptr )
{
makeEmpty( t->left );
makeEmpty( t->right );
delete t;
}
t = nullptr;
}
/**
* Internal method to print a subtree rooted at t in sorted order.
*/
void printTree( BinaryNode *t, ostream & out ) const
{
if( t != nullptr )
{
printTree( t->left, out );
out << t->element << endl;
printTree( t->right, out );
}
}
/**
* Internal method to clone subtree.
*/
BinaryNode * clone( BinaryNode *t ) const
{
if( t == nullptr )
return nullptr;
else
return new BinaryNode{ t->element, clone( t->left ), clone( t->right ) };
}
/**
* Return tree walks of a subtree rooted at b_node of
* three types as a vector of elements in the tree
* 0 - preorder, 1 - inorder, 2 - postorder
*/
int treeWalk(BinaryNode *b_node, int type, vector<Comparable> & t_walk){
if (type<0 || type>2){
cout << "Invalid type of tree walk" << endl;
return -1;
}
if (b_node==NULL)
return 0;
int walk_done1, walk_done2;
switch(type){
case 0: t_walk.push_back(b_node->element);
walk_done1 = treeWalk(b_node->left, type, t_walk);
walk_done2 = treeWalk(b_node->right, type, t_walk);
break;
case 1: walk_done1 = treeWalk(b_node->left, type, t_walk);
t_walk.push_back(b_node->element);
walk_done2 = treeWalk(b_node->right, type, t_walk);
break;
case 2: walk_done1 = treeWalk(b_node->left, type, t_walk);
walk_done2 = treeWalk(b_node->right, type, t_walk);
t_walk.push_back(b_node->element);
break;
}
if (walk_done1 != 0 || walk_done2 != 0){
cout << "Something is wrong." << endl;
return -1;
}
return 0;
}
};
#endif
Here is the cpp code
TestBinarySearchTree.cpp
#include <iostream>
#include "BinarySearchTree.h"
using namespace std;
// Test program
int main( )
{
BinarySearchTree<int> t;
int NUMS = 400000;
const int GAP = 3711;
int i;
cout << "Checking... (no more output means success)" << endl;
for( i = GAP; i != 0; i = ( i + GAP ) % NUMS )
t.insert( i );
for( i = 1; i < NUMS; i+= 2 )
t.remove( i );
if( NUMS < 40 )
t.printTree( );
if( t.findMin( ) != 2 || t.findMax( ) != NUMS - 2 )
cout << "FindMin or FindMax error!" << endl;
for( i = 2; i < NUMS; i+=2 )
if( !t.contains( i ) )
cout << "Find error1!" << endl;
for( i = 1; i < NUMS; i+=2 )
{
if( t.contains( i ) )
cout << "Find error2!" << endl;
}
BinarySearchTree<int> t2;
t2 = t;
for( i = 2; i < NUMS; i+=2 )
if( !t2.contains( i ) )
cout << "Find error1!" << endl;
for( i = 1; i < NUMS; i+=2 )
{
if( t2.contains( i ) )
cout << "Find error2!" << endl;
}
// The following code randomly builds a BST and
// display all the three tree walks of the built tree.
BinarySearchTree<int> t3;
int numNodes = 10;
cout << "Building a random BST..." << endl;
srand(time(NULL));
for (i = 0; i< numNodes; i++)
t3.insert(rand()%1000);
cout << "Finished building a random BST." << endl;
cout << "Printing tree walks: " << endl;
t3.displayTreeWalk(0);
t3.displayTreeWalk(1);
t3.displayTreeWalk(2);
cout << "Finished testing" << endl;
return 0;
}