For this computer assignment using c++ implement a derived class to represent a
ID: 3806301 • Letter: F
Question
For this computer assignment using c++ implement a derived class to represent a binary search tree. Since a binary search tree is also a binary tree, implement your binary search tree class from the base class of binary trees. Implement the following functions in to the code that is provided. The above public functions simply call their private versions. The private versions of insert (), remove (), search() and sumOfRange () functions can be implemented as recursive functions. You can assume there are no identical numbers to be inserted into the tree.
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
static const int SEARCH_LOW = 20;
static const int SEARCH_HIGH = 30;
static const int MAX_COUNT = 20;
static int mcount = 0;
class BST : public binTree
{
public:
BST() : binTree() {}
void insert(int);
bool search(int);
bool remove(int);
int sumOfRange(int lower, const int upper);
private:
void insert(Node*&, int);
bool search(Node*&, int);
bool remove(Node*&, int);
int sumOfRange(Node*& n, const int lower, const int upper);
};
void display2(int d) {
if (mcount < MAX_COUNT) {
cout << setw(4) << d;
mcount++;
}
}
// produce a random number within range [1 1000]
int rand_1000() {
return rand() % 1000 + 1;
}
void show_tree_information(BST& bst) {
cout << "Size of the tree: " << bst.size() << endl;
cout << "Height of the tree: " << bst.height() << endl;
cout << "In order traverse (displaying first " << MAX_COUNT << " numbers): " << endl;
mcount = 0;
bst.inorder(display2);
cout << " Pre order traverse (displaying first " << MAX_COUNT << " numbers): " << endl;
mcount = 0;
bst.preorder(display2);
cout << " Post order traverse (displaying first " << MAX_COUNT << " numbers): " << endl;
mcount = 0;
bst.postorder(display2);
}
// For each value in searchVec, search it in the binary search tree
// and report the number of successful searches
void run_search(BST& bst, vector<int>& searchVec) {
int success = 0;
vector<int>::iterator it;
for (it = searchVec.begin(); it != searchVec.end(); it++)
if (bst.search(*it))
success++;
cout << endl << endl << "Out of " << searchVec.size() << " searches, " << success << " are successful." << endl << endl;
}
int main() {
//-------------- Create a B.S.T. using unique random numbers -----------
vector<int> inputVec(1000);
srand(7);
generate(inputVec.begin(), inputVec.end(), rand_1000);
sort(inputVec.begin(), inputVec.end());
vector<int>::iterator it = unique(inputVec.begin(), inputVec.end());
inputVec.resize(it - inputVec.begin());
random_shuffle(inputVec.begin(), inputVec.end());
BST bst;
for (it = inputVec.begin(); it != inputVec.end(); it++)
bst.insert(*it);
cout << "A binary search tree is generated with random numbers: " << endl;
show_tree_information(bst);
//-------------- Create a vector of random integers to be searched ------
vector<int> searchVec(500);
srand(11);
generate(searchVec.begin(), searchVec.end(), rand_1000);
//cout << endl << endl << "Sum of range: " << bst.sumOfRange(SEARCH_LOW, SEARCH_HIGH) << endl;
//------------ test search operations ----------------
run_search(bst, searchVec);
//------------ remove half of nodes from the tree ---------
int counter = 0;
random_shuffle(inputVec.begin(), inputVec.end());
for (it = inputVec.begin(); it < inputVec.end(); it += 2) {
if (bst.remove(*it))
counter++;
}
cout << endl << counter << " nodes are removed." << endl << endl;
show_tree_information(bst);
cout << endl << endl << "Sum of range between " << SEARCH_LOW << " and "
<< SEARCH_HIGH << " : " << bst.sumOfRange(SEARCH_LOW, SEARCH_HIGH) << endl;
//-------------- test search operations again ---------------
run_search(bst, searchVec);
return 0;
}
Explanation / Answer
//Code for insert search and remove methods of BST class
//Add this functions to your code and run it.
void BST::insert(Node*& t,int a)
{
if(head==NULL)
{
Node *temp=new Node();
temp->data=a;
temp->left=temp->right=NULL;
head=temp;
return;
}
if(head->data>a)
insert(head->left,a);
else
insert(head->right,a);
}
void BST::insert(int a)
{
insert(head,a);
}
bool BST::search(Node*& t,int a)
{
if(head==NULL)
return false;
if(head->data==a)
return true;
else if(head->data>a)
return (search(head->left,a));
else if(head->data<a)
return (search(head->right,a));
return false;
}
bool BST::search(int a)
{
return search(head,a);
}
/* Given a non-empty binary search tree, return the node with minimum
key value found in that tree. Note that the entire tree does not
need to be searched. */
Node* minValueNode(Node* node)
{
Node* current = node;
/* loop down to find the leftmost leaf */
while (current->left != NULL)
current = current->left;
return current;
}
bool BST::remove(Node*& head,int a)
{
// base case
if (head == NULL) return false;
// If the key to be deleted is smaller than the root's key,
// then it lies in left subtree
if (a < head->data)
// root->left = deleteNode(root->left, key);
remove(head->left,a);
// If the key to be deleted is greater than the root's key,
// then it lies in right subtree
else if (a > head->data)
remove(head->right,a);
// root->right = deleteNode(root->right, key);
// if key is same as root's key, then This is the node
// to be deleted
else
{
// node with only one child or no child
if (head->left == NULL)
{
Node* temp = head;
head=head->right;
free(temp);
return true;
}
else if (head->right == NULL)
{
Node* temp = head;
head=head->left;
free(temp);
return true;
}
// node with two children: Get the inorder successor (smallest
// in the right subtree)
Node* temp = minValueNode(head->right);
// Copy the inorder successor's content to this node
head->data = temp->data;
// Delete the inorder successor
remove(head->right, temp->data);
}
return true;
}
bool BST::remove(int a)
{
return remove(head,a);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.