The following needs to be done in C++, after the task itself is the program I ha
ID: 3587601 • Letter: T
Question
The following needs to be done in C++, after the task itself is the program I have so far prior to this task.
Create a SimpleBag class that uses a binary search tree to store the bag items. The class should have the methods listed below. Test your SimpleBag class.
SimpleBag(): default constructor; creates an empty bag
bool isEmpty(): determines whether the bag is empty
void print(): prints the SimpleBag elements
void clear(): removes all of the items from the bag
void add(int item): adds an item to the bag
int count(int item): counts the number of occurrences of item in the bag
main.cpp
/********************************************
* Week 6 lesson: *
* implementation of a binary search tree *
*********************************************/
#include <iostream>
#include "BinarySearchTree.h"
#include "time.h"
using namespace std;
int main()
{
BinarySearchTree bst;
int x;
if (bst.isEmpty()) cout << "BST is empty" << endl;
else cout << "BST is not empty" << endl;
srand((unsigned int)time(0));
for (int i=0; i < 10; i++)
bst.add(rand()%20);
if (bst.isEmpty()) cout << "BST is empty" << endl;
else cout << "BST is not empty" << endl;
bst.display();
x = rand()%20;
if (bst.search(x)) cout << x << " was found!"<< endl;
else cout << x << " was not found!"<< endl;
cout << "Minimum of the tree = " << bst.getMinimum() << endl;
return 0;
}
BinarySearchTree.h
/********************************************
* Week 6 lesson: *
* implementation of a binary search tree *
*********************************************/
/*
* Binary search tree node.
*/
struct TreeNode
{
int info; //element stored in this node
TreeNode *left; //link to left child
TreeNode *right; //link to right child
};
/*
* Class implementing a binary search tree.
*/
class BinarySearchTree
{
public:
BinarySearchTree();
bool isEmpty();
void display();
bool search(int);
void add(int);
int getMinimum();
~BinarySearchTree();
private:
TreeNode* root;
void inorderDisplay(TreeNode*);
bool search(int, TreeNode*);
void add(int, TreeNode* &);
TreeNode* getMinimum(TreeNode*);
void deallocateMemory(TreeNode* &);
};
BinarySearchTree.cpp
/********************************************
* Week 6 lesson: *
* implementation of a binary search tree *
*********************************************/
#include <iostream>
#include "BinarySearchTree.h"
using namespace std;
//Public functions
/*
* Initializes the bst to empty.
*/
BinarySearchTree::BinarySearchTree()
{
root = NULL;
}
/*
* Determines whether the bst is empty
*
* Returns true if the bst is empty, false otherwise
*/
bool BinarySearchTree::isEmpty()
{
return root == NULL;
}
/*
* Prints the bst elements using inorder traversal. This method invokes the
* private method inorderDisplay, passing to it the root of the actual tree.
*/
void BinarySearchTree::display()
{
inorderDisplay(root);
cout << endl;
}
/*
* Determines if an item exists in the bst. This method invokes the private
* method search, passing to it the element to be found and the root
* of the actual tree.
*
* x: element to be found.
*
* Returns true if x is found in the bst, false otherwise.
*/
bool BinarySearchTree::search(int x)
{
return search(x, root);
}
/*
* Adds the element x to the bst. This method invokes the private method
* add, passing to it the element to be added to the bst and the root
* of the actual tree.
*
* x: element to be added to the bst.
*/
void BinarySearchTree::add(int x)
{
add(x, root);
}
/*
* Finds the smallest value in the bst. This method invokes the overloaded
* method getMinimum, passing to it the root of the tree.
*
* Returns the smallest value in the bst.
*/
int BinarySearchTree::getMinimum()
{
return getMinimum(root)->info;
}
/*
* Destructor. Invokes the method deallocateMemory, passing to it the root
* of the tree.
*/
BinarySearchTree::~BinarySearchTree()
{
deallocateMemory(root);
}
//Private functions
/*
* Prints the elements of the subtree whose root is pointed to by p. Uses
* inorder traversal.
*
* p: root of subtree.
*/
void BinarySearchTree::inorderDisplay(TreeNode *p)
{
if (p != NULL)
{
inorderDisplay(p->left);
cout << p->info << " ";
inorderDisplay(p->right);
}
}
/*
* Adds x to the subtree pointed to by p. The search for the location to
* insert the new node is conducted recursively, using the bst property:
* keys in the left subtree of a node are smaller than or equal to the key
* in the node, while the keys in the right subtree of the node are greater.
*
* x: element to be added to the subtree.
* p: root of subtree.
*/
void BinarySearchTree::add(int x, TreeNode* & p)
{
if (p == NULL)
{
p = new TreeNode;
p->info = x;
p->left = p->right = NULL;
}
else
{
if (x <= p->info) add(x, p->left);
else add(x, p->right);
}
}
/*
* Finds if x is present in the subtree whose root is pointed to by p. The
* search is conducted recursively, using the bst property: keys in the left
* subtree of a node are smaller than or equal to the key in the node, while
* the keys in the right subtree of the node are greater.
*
* x: element to be found.
* p: root of subtree.
*
* Returns true if x is found in this subtree, false otherwise.
*/
bool BinarySearchTree::search(int x, TreeNode* p)
{
if (p == NULL) return false;
else
if (x == p->info) return true;
else
if (x < p->info) return search(x, p->left);
else return search(x, p->right);
}
/*
* Recursively finds the smallest value in the subtree pointed to by p.
* The method uses this property of BSTs: the smallest value is stored in
* the leftmost node.
*
* p: root of subtree.
*
* Returns smallest value in the subtree pointed to by p.
*/
TreeNode* BinarySearchTree::getMinimum(TreeNode* p)
{
if (p->left == NULL) return p;
else return getMinimum(p->left);
}
/*
* Recursively deallocates the memory of the subtree pointed to by p.
*
* p: root of subtree.
*/
void BinarySearchTree::deallocateMemory(TreeNode* & p)
{
if (p != NULL)
{
deallocateMemory(p->left);
deallocateMemory(p->right);
delete p;
p = NULL;
}
}
Explanation / Answer
#include <iostream>
#include <math.h>
using namespace std;
struct node
{
int key_value;
node *left;
node *right;
};
class SimpleBag
{
public:
SimpleBag()
{
root = NULL;
}
~SimpleBag()
{
destroy_tree();
}
void insert (int key)
{
if(root != NULL){
insert(key, root);
}else
{
root = new node();
root->key_value = key;
root->left = NULL;
root->right = NULL;
}
}
node *search(int key)
{
return search(key, root);
}
void destroy_tree()
{
destroy_tree(root);
}
bool isEmpty()
{
return root == NULL;
}
void print()
{
printHelper(root);
}
private:
void destroy_tree(node *leaf)
{
if(leaf != NULL)
{
destroy_tree(leaf->left);
destroy_tree(leaf->right);
delete leaf;
}
}
void insert(int key, node *leaf)
{
if(key < leaf->key_value)
{
if(leaf->left != NULL){
insert(key,leaf->left);
}else
{
leaf->left = new node;
leaf->left->key_value = key;
leaf->left->left = NULL;
leaf->left->right = NULL;
}
}
else if(key >= leaf->key_value)
{
if(leaf->right != NULL){
insert(key,leaf->right);
}else
{
leaf->right = new node;
leaf->right->key_value=key;
leaf->right->left=NULL;
leaf->right->right=NULL;
}
}
}
node *search(int key, node *leaf)
{
if(leaf != NULL)
{
if(key == leaf->key_value){
return leaf;
}
if(key < leaf->key_value){
return search(key, leaf->left);
}else{
return search(key, leaf->right);
}
}
else return NULL;
}
void printHelper(node *leaf)
{
if(leaf == NULL) return;
printHelper(leaf->left);
cout<<leaf->key_value<<" ";
printHelper(leaf->right);
}
node *root;
};
int main()
{
SimpleBag bst;
if(bst.isEmpty()){
cout<<"Bag is empty";
}else{
cout<<"Bag is not empty";
}
bst.insert(10);
bst.insert(12);
bst.insert(5);
bst.insert(3);
bst.insert(57);
if(bst.isEmpty()){
cout<<"Bag is empty";
}else{
cout<<"Bag is not empty";
}
cout<<"displying all the elements";
bst.print();
if(bst.search(5) ==NULL){
cout<<"key 5 is not found";
}else{
cout<<" key 5 is found in the bag";
}
cout<<"clearing the bag contents";
bst.destroy_tree();
if(bst.isEmpty()){
cout<<"Bag is empty";
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.