Write a C++ program to implement a binary search tree and operate on the binary
ID: 3600918 • Letter: W
Question
Write a C++ program to implement a binary search tree and operate on the binary search tree, which to hold integers with no duplicate starting root = null. All of base code is given, need to add all necessary code.
Each line should have an explanation.
# include
# include
# include
# include
# include
# include
# include
using namespace std;
struct node
{
//Define
}*root;
Class BST
{
Public:
find
insert
del
BST()
{
root = NULL;
}
};
int main()
{
int choice, num;
string command;
BST bst;
node *temp;
cout<<"-----------------"<
cout<<"Operations on BST"<
cout<<"-----------------"<
cout<<"INSERT "<
cout<<"DELETE "<
cout<<"FIND "<
cout<<"PRINT "<
cout<<"EXIT "<
cout<<"Continue to enter your choice, type EXIT when you are done.";
while (1)
{
vector data;
copy(istream_iterator(cin), istream_iterator(), back_inserter(data));
command = data[0];
transform(command.begin(), command.end(), command.begin(), ::toupper);
if (command == “INSERT”)
{
}
else if (command == “DELETE”)
{
}
else if (command == “FIND”)
{
}
else if (command == “PRINT”)
{
}
else if (command == “EXIT”)
{
exit(1);
}
else
{
cout<<”Wrong choice”<
}
}
}
INSERT <int value>
Output : SUCCESS or DUPLICATE or ERROR
DELETE <int value>
Output : SUCCESS or NOTFOUND or ERROR
FIND <int value>
Output : SUCCESS or NOTFOUND or ERROR
Output : PRINT NULL, if the tree is empty, otherwise print the numbers in sorted order(one per line) and print BEGIN at the start and END at the end(last line).
EXIT
The program is terminated.
Here is sample run:
Sample input
Sample output
NULL
INSERT 7
SUCCESS
INSERT 10
SUCCESS
INSERT 98
SUCCESS
INSERT 6
SUCCESS
INSERT 10
DUPLICATE
FIND 98
SUCCESS
FIND 34
NOTFOUND
DELETE 10
SUCCESS
BEGIN
6
7
98
END
EXIT
N/A (Program exits)
Sample input
Sample output
NULL
INSERT 7
SUCCESS
INSERT 10
SUCCESS
INSERT 98
SUCCESS
INSERT 6
SUCCESS
INSERT 10
DUPLICATE
FIND 98
SUCCESS
FIND 34
NOTFOUND
DELETE 10
SUCCESS
BEGIN
6
7
98
END
EXIT
N/A (Program exits)
Explanation / Answer
Note: please make changes in the vector and istream_iterator code rest of the code is working fine.
#include <iostream> //for std input output
#include <stdlib.h> //for the exit() function
#include <vector>
#include<iterator>
using namespace std;
struct node
{
int data;
node *left;
node *right;
}*root;
class BST
{
public:
void find(int);
void insert(int);
void del(int);
void print(node*);
BST()
{
root = NULL;
}
};
void BST::find(int d){
node* curr;
curr = root;
while(curr){
if(curr->data == d){
cout<<"FOUND"<<endl;
return;
}
else if (curr->data < d)
curr = curr->right;
else
curr = curr->left;
}
cout<<"NOT FOUND"<<endl;
return;
}
void BST::insert(int d){
node* temp = new node;
node* parent = NULL;
temp->data = d;
temp->left = NULL;
temp->right = NULL;
if(root == NULL)
root= temp;
else{
node* curr;
curr = root;
while(curr){
parent = curr;
if(temp->data > curr->data)
curr = curr->right;
else
curr = curr->left;
}
if(temp->data < parent->data)
parent->left = temp;
else
parent->right = temp;
}
}
void BST::del(int d){
bool found = false;
if(root==NULL){
cout << "The tree is empty ";
return;
}
node* curr= root;
node* parent;
while(curr != NULL){
if(curr->data == d){
found = true;
break;
}
else{
parent = curr;
if(d>curr->data) curr = curr->right;
else curr = curr->left;
}
}
if(!found)
{
cout<<" Data not found! "<<endl;
return;
}
// 3 cases :
// 1. We're removing a leaf node
// 2. We're removing a node with a single child
// 3. we're removing a node with 2 children
// Node with single child
if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL
&& curr->right == NULL))
{
if(curr->left == NULL && curr->right != NULL)
{
if(parent->left == curr)
{
parent->left = curr->right;
delete curr;
}
else
{
parent->right = curr->right;
delete curr;
}
}
else // left child present, no right child
{
if(parent->left == curr)
{
parent->left = curr->left;
delete curr;
}
else
{
parent->right = curr->left;
delete curr;
}
}
cout<<"SUCESS"<<endl;
return;
}
//We're looking at a leaf node
if( curr->left == NULL && curr->right == NULL)
{
if(parent->left == curr) parent->left = NULL;
else parent->right = NULL;
delete curr;
cout<<"SUCESS"<<endl;
return;
}
//Node with 2 children
// replace node with smallest value in right subtree
if (curr->left != NULL && curr->right != NULL)
{
node* r;
r = curr->right;
if((r->left == NULL) && (r->right == NULL))
{
curr = r;
delete r;
curr->right = NULL;
}
else // right child has children
{
//if the node's right child has a left child
// Move all the way down left to locate smallest element
if((curr->right)->left != NULL)
{
node* l;
node* lp;
lp = curr->right;
l = (curr->right)->left;
while(l->left != NULL)
{
lp = l;
l = l->left;
}
curr->data = l->data;
delete l;
lp->left = NULL;
}
else
{
node* tmp;
tmp = curr->right;
curr->data = tmp->data;
curr->right = tmp->right;
delete tmp;
}
}
cout<<"SUCESS"<<endl;
return;
}
}
void BST::print(node* p){
if(p != NULL)
{
if(p->left) print(p->left);
cout<<" "<<p->data<<" "<<endl;
if(p->right) print(p->right);
}
else return;
}
int main()
{
int choice, num;
string command;
BST bst;
node *temp;
cout<<"-----------------"<<endl;
cout<<"Operations on BST"<<endl;
cout<<"-----------------"<<endl;
cout<<"INSERT "<<endl;
cout<<"DELETE "<<endl;
cout<<"FIND "<<endl;
cout<<"PRINT "<<endl;
cout<<"EXIT "<<endl;
cout<<"Continue to enter your choice, type EXIT when you are done."<<endl;
while (1)
{
vector<string> data;
copy(istream_iterator(cin), istream_iterator(), back_inserter(data));
command = data[0];
transform(command.begin(), command.end(), command.begin(), ::toupper);
if(command == "INSERT")
{
cin>>num;
bst.insert(num);
break;
}
else if (command == "DELETE")
{
cin>>num;
bst.del(num);
}
else if (command == "FIND")
{
}
else if (command == "PRINT")
{
if (root == NULL)
cout<<"NULL"<<endl;
else{
cout << "BEGIN"<<endl;
bst.print(root);
cout << "END"<<endl;
}
break;
}
else if (command == "EXIT")
{
exit(1);
}
else
{
cout<<"Wrong choice"<<endl;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.