I need a c++ code to implement a binary search tree (BST) which stores integers
ID: 3832997 • Letter: I
Question
I need a c++ code to implement a binary search tree (BST) which stores integers that you will read from a file. Your BST will have an add, delete, print, find, and rangeFind function. This assignment is based on common job interview questions that involve BST. Extra Credit: Implement with node heights. Use the height to print the tree with branch lengths. Example I/O: Without errors: File name: numbers.txt Delete (d), Print (p), Find (f), RangeFind (r), Quit (q) p 3 5 6 7 8 10 11 13 15 16 17 19 20 23 24 26 29 30 34 34 40 f Find: 20 Value found f Find: 29 Value found f Find: 18 Value not found. The closest value is: 17 f Find: 90 Value not found. The closest value is: 40 r Range Min: 11 Range Max: 22 11 13 15 16 17 19 20 d Delete: 43 43 Not found in BST. d Delete: 7 p 3 5 6 8 10 11 13 15 16 17 19 20 23 24 26 29 30 34 34 40 q
Explanation / Answer
}
********************************************************************************
#include <iostream> #include <math.h> using namespace std; template <class T> struct Node { T value; Node *left; Node *right; Node(T val) { this->value = val; } Node(T val, Node<T> left, Node<T> right) { this->value = val; this->left = left; this->right = right; } }; template <class T> class BST { private: Node<T> *root; void addHelper(Node<T> *root, T val) { if (root->value > val) { if (!root->left) { root->left = new Node<T>(val); } else { addHelper(root->left, val); } } else { if (!root->right) { root->right = new Node<T>(val); } else { addHelper(root->right, val); } } } void printHelper(Node<T> *root) { if (!root) return; printHelper(root->left); cout<<root->value<<' '; printHelper(root->right); } int nodesCountHelper(Node<T> *root) { if (!root) return 0; else return 1 + nodesCountHelper(root->left) + nodesCountHelper(root->right); } int heightHelper(Node<T> *root) { if (!root) return 0; else return 1 + max(heightHelper(root->left), heightHelper(root->right)); } void printMaxPathHelper(Node<T> *root) { if (!root) return; cout<<root->value<<' '; if (heightHelper(root->left) > heightHelper(root->right)) { printMaxPathHelper(root->left); } else { printMaxPathHelper(root->right); } } bool deleteValueHelper(Node<T>* parent, Node<T>* current, T value) { if (!current) return false; if (current->value == value) { if (current->left == NULL || current->right == NULL) { Node<T>* temp = current->left; if (current->right) temp = current->right; if (parent) { if (parent->left == current) { parent->left = temp; } else { parent->right = temp; } } else { this->root = temp; } } else { Node<T>* validSubs = current->right; while (validSubs->left) { validSubs = validSubs->left; } T temp = current->value; current->value = validSubs->value; validSubs->value = temp; return deleteValueHelper(current, current->right, temp); } delete current; return true; } return deleteValueHelper(current, current->left, value) || deleteValueHelper(current, current->right, value); } public: void add(T val) { if (root) { this->addHelper(root, val); } else { root = new Node<T>(val); } } void print() { printHelper(this->root); } int nodesCount() { return nodesCountHelper(root); } int height() { return heightHelper(this->root); } void printMaxPath() { printMaxPathHelper(this->root); } bool deleteValue(T value) { return this->deleteValueHelper(NULL, this->root, value); } }; int main() { BST<int> *bst = new BST<int>(); bst->add(11); bst->add(1); bst->add(6); bst->add(-1); bst->add(-10); bst->add(100); bst->print(); cout<<endl; cout<<"Nodes count: "<<bst->nodesCount(); cout<<endl; cout<<"Height: "<<bst->height(); cout<<endl; cout<<"Max path: "; bst->printMaxPath(); cout<<endl; bst->deleteValue(11); cout<<"11 removed: "; bst->print(); cout<<endl; cout<<"1 removed: "; bst->deleteValue(1); bst->print(); cout<<endl; cout<<"-1 removed: "; bst->deleteValue(-1); bst->print(); cout<<endl; cout<<"6 removed: "; bst->deleteValue(6); bst->print(); cout<<endl; cout<<"-10 removed: "; bst->deleteValue(-10); bst->print(); cout<<endl; cout<<"100 removed: "; bst->deleteValue(100); bst->print(); cout<<endl; return 0;}
********************************************************************************
# include <iostream>
# include <cstdlib>
using namespace std;
struct node
{ int info;
struct node *left;
struct node *right;
}*root;
class BST { public:
void find(int, node **, node **);
void insert(int);
void del(int);
void case_a(node *,node *);
void case_b(node *,node *);
void case_c(node *,node *);
void preorder(node *);
void inorder(node *);
void postorder(node *);
void display(node *, int);
BST()
{ root = NULL;
}
};
int main()
{ int choice, num;
BST bst;
node *temp;
while (1)
{ cout<<"-----------------"<<endl;
cout<<"Operations on BST"<<endl;
cout<<"-----------------"<<endl;
cout<<"1.Insert Element "<<endl;
cout<<"2.Delete Element "<<endl;
cout<<"3.Inorder Traversal"<<endl;
cout<<"4.Preorder Traversal"<<endl;
cout<<"5.Postorder Traversal"<<endl;
cout<<"6.Display"<<endl;
cout<<"7.Quit"<<endl;
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{ case 1:
temp = new node;
cout<<"Enter the number to be inserted : ";
cin>>temp->info;
bst.insert(root, temp);
case 2:
if (root == NULL)
{ cout<<"Tree is empty, nothing to delete"<<endl;
continue;
}
cout<<"Enter the number to be deleted : ";
cin>>num;
bst.del(num);
break;
case 3:
cout<<"Inorder Traversal of BST:"<<endl;
bst.inorder(root);
cout<<endl;
break;
case 4:
cout<<"Preorder Traversal of BST:"<<endl;
bst.preorder(root);
cout<<endl;
break;
case 5:
cout<<"Postorder Traversal of BST:"<<endl;
bst.postorder(root);
cout<<endl;
break;
case 6:
cout<<"Display BST:"<<endl;
bst.display(root,1);
cout<<endl;
break;
case 7:
exit(1);
default:
cout<<"Wrong choice"<<endl;
}
}
}
void BST::find(int item, node **par, node **loc)
{ node *ptr, *ptrsave;
if (root == NULL)
{ *loc = NULL;
*par = NULL;
return;
}
if (item == root->info)
{ *loc = root;
*par = NULL;
return;
}
if (item < root->info)
ptr = root->left;
else
ptr = root->right;
ptrsave = root;
while (ptr != NULL)
{ if (item == ptr->info)
{ *loc = ptr;
*par = ptrsave;
return;
}
ptrsave = ptr;
if (item < ptr->info)
ptr = ptr->left;
else
ptr = ptr->right;
}
*loc = NULL;
*par = ptrsave;
}
void BST::insert(node *tree, node *newnode)
{ if (root == NULL)
{ root = new node;
root->info = newnode->info;
root->left = NULL;
root->right = NULL;
cout<<"Root Node is Added"<<endl;
return;
}
if (tree->info == newnode->info)
{ cout<<"Element already in the tree"<<endl;
return;
}
if (tree->info > newnode->info)
{ if (tree->left != NULL)
{ insert(tree->left, newnode);
}
else
{ tree->left = newnode;
(tree->left)->left = NULL;
(tree->left)->right = NULL;
cout<<"Node Added To Left"<<endl;
return;
}
}
else
{ if (tree->right != NULL)
{ insert(tree->right, newnode);
}
else
{ tree->right = newnode;
(tree->right)->left = NULL;
(tree->right)->right = NULL;
cout<<"Node Added To Right"<<endl;
return;
}
}
}
void BST::del(int item)
{ node *parent, *location;
if (root == NULL)
{ cout<<"Tree empty"<<endl;
return;
}
find(item, &parent, &location);
if (location == NULL)
{ cout<<"Item not present in tree"<<endl;
return;
}
if (location->left == NULL && location->right == NULL)
case_a(parent, location);
if (location->left != NULL && location->right == NULL)
case_b(parent, location);
if (location->left == NULL && location->right != NULL)
case_b(parent, location);
if (location->left != NULL && location->right != NULL)
case_c(parent, location);
free(location);
}
void BST::case_a(node *par, node *loc )
{ if (par == NULL)
{ root = NULL;
}
else
{ if (loc == par->left)
par->left = NULL;
else
par->right = NULL;
}
}
void BST::case_b(node *par, node *loc)
{ node *child;
if (loc->left != NULL)
child = loc->left;
else
child = loc->right;
if (par == NULL)
{ root = child;
}
else
{ if (loc == par->left)
par->left = child;
else
par->right = child;
}
}
void BST::case_c(node *par, node *loc)
{ node *ptr, *ptrsave, *suc, *parsuc;
ptrsave = loc;
ptr = loc->right;
while (ptr->left != NULL)
{ ptrsave = ptr;
ptr = ptr->left;
}
suc = ptr;
parsuc = ptrsave;
if (suc->left == NULL && suc->right == NULL)
case_a(parsuc, suc);
else
case_b(parsuc, suc);
if (par == NULL)
{ root = suc;
}
else
{ if (loc == par->left)
par->left = suc;
else
par->right = suc;
}
suc->left = loc->left;
suc->right = loc->right;
}
void BST::preorder(node *ptr)
{ if (root == NULL)
{ cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{ cout<<ptr->info<<" ";
preorder(ptr->left);
preorder(ptr->right);
}
}
void BST::inorder(node *ptr)
{ if (root == NULL)
{ cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{ inorder(ptr->left);
cout<<ptr->info<<" ";
inorder(ptr->right);
}
}
void BST::postorder(node *ptr)
{ if (root == NULL)
{ cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{ postorder(ptr->left);
postorder(ptr->right);
cout<<ptr->info<<" ";
}
}
void BST::display(node *ptr, int level)
{ int i;
if (ptr != NULL)
{ display(ptr->right, level+1);
cout<<endl;
if (ptr == root)
cout<<"Root->: ";
else
{ for (i = 0;i < level;i++)
cout<<" ";
}
cout<<ptr->info;
display(ptr->left, level+1);
}
}
Related Questions
Hire Me For All Your Tutoring Needs
Integrity-first tutoring: clear explanations, guidance, and feedback.
Drop an Email at
drjack9650@gmail.com
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.