Homework Soursecreate a binary search tree from an empty one by adding the
create a binary search tree from an empty one by adding the key value alphabetically in c++
Solution
//Binary Search Tree Program
#include <iostream>
#include <cstdlib>
using namespace std;
class BinarySearchTree
{
private:
struct tree_node //structure to hold Binary search tree
{
tree_node* left;
tree_node* right;
int data;
};
tree_node* root;
public:
BinarySearchTree() //constructor of Binary search tree
{
root = NULL;
}
//function declarations
bool isEmpty() const { return root==NULL; }
void print_inorder();
void inorder(tree_node*);
void print_preorder();
void preorder(tree_node*);
void print_postorder();
void postorder(tree_node*);
void insert(int);
void remove(int);
};
// Smaller elements go left
// larger elements go right
void BinarySearchTree::insert(int d) //insert function to BST
{
tree_node* t = new tree_node;
tree_node* parent;
t->data = d;
t->left = NULL;
t->right = NULL;
parent = NULL;
// is this a new tree?
if(isEmpty()) root = t;
else
{
//Note: ALL insertions are as leaf nodes
tree_node* curr;
curr = root;
// Find the Node\'s parent
while(curr)
{
parent = curr;
if(t->data > curr->data) curr = curr->right;
else curr = curr->left;
}
if(t->data < parent->data)
parent->left = t;
else
parent->right = t;
}
}
void BinarySearchTree::remove(int d)
{
//Locate the element
bool found = false;
if(isEmpty())
{
cout<<\" This Tree is empty! \"<<endl;
return;
}
tree_node* curr;
tree_node* parent;
curr = root;
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;
}
}
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;
return;
}
//Node with 2 children
// replace node with smallest value in right subtree
if (curr->left != NULL && curr->right != NULL)
{
tree_node* chkr;
chkr = curr->right;
if((chkr->left == NULL) && (chkr->right == NULL))
{
curr = chkr;
delete chkr;
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)
{
tree_node* lcurr;
tree_node* lcurrp;
lcurrp = curr->right;
lcurr = (curr->right)->left;
while(lcurr->left != NULL)
{
lcurrp = lcurr;
lcurr = lcurr->left;
}
curr->data = lcurr->data;
delete lcurr;
lcurrp->left = NULL;
}
else
{
tree_node* tmp;
tmp = curr->right;
curr->data = tmp->data;
curr->right = tmp->right;
delete tmp;
}
}
return;
}
}
void BinarySearchTree::print_inorder()
{
inorder(root);
}
void BinarySearchTree::inorder(tree_node* p) //defination of in order ,calls recursivily left,display root element and recursivily calls right parts
{
if(p != NULL)
{
if(p->left) inorder(p->left);
cout<<\" \"<<p->data<<\" \";
if(p->right) inorder(p->right);
}
else return;
}
void BinarySearchTree::print_preorder()
{
preorder(root);
}
void BinarySearchTree::preorder(tree_node* p) //defination of pre order ,display root & calls recursivily left,right parts
{
if(p != NULL)
{
cout<<\" \"<<p->data<<\" \";
if(p->left) preorder(p->left);
if(p->right) preorder(p->right);
}
else return;
}
void BinarySearchTree::print_postorder()
{
postorder(root);
}
void BinarySearchTree::postorder(tree_node* p) //defination of post order ,calls recursivily left,right parts and display final element
{
if(p != NULL)
{
if(p->left) postorder(p->left);
if(p->right) postorder(p->right);
cout<<\" \"<<p->data<<\" \";
}
else return;
}
int main()
{
BinarySearchTree b;
int ch,tmp,tmp1;
//Loop for getting user choice
while(1)
{
//Menu displayed to user
cout<<endl<<endl;
cout<<\" Binary Search Tree Operations \"<<endl;
cout<<\" ----------------------------- \"<<endl;
cout<<\" 1. Insertion/Creation \"<<endl;
cout<<\" 2. In-Order Traversal \"<<endl;
cout<<\" 3. Pre-Order Traversal \"<<endl;
cout<<\" 4. Post-Order Traversal \"<<endl;
cout<<\" 5. Removal \"<<endl;
cout<<\" 6. Exit \"<<endl;
cout<<\" Enter your choice : \";
cin>>ch;
switch(ch)
{
case 1 : cout<<\" Enter Number to be inserted : \"; //prompt & read inserting number
cin>>tmp;
b.insert(tmp); //call insert function with argument
break;
case 2 : cout<<endl;
cout<<\" Display In-Order Traversal \"<<endl;
cout<<\" -------------------\"<<endl;
b.print_inorder(); //call in order function to display
break;
case 3 : cout<<endl;
cout<<\"Display Pre-Order Traversal \"<<endl;
cout<<\" -------------------\"<<endl;
b.print_preorder(); //call pre order function to display
break;
case 4 : cout<<endl;
cout<<\" Display Post-Order Traversal \"<<endl;
cout<<\" --------------------\"<<endl;
b.print_postorder(); //call in post order function to display
break;
case 5 : cout<<\" Enter data to be removed : \";
cin>>tmp1;
b.remove(tmp1); //remove element function call
break;
case 6 : system(\"pause\"); //exit Menu code
return 0;
break;
}
}
}
Output :
Binary Search Tree Operations
-----------------------------
1. Insertion/Creation
2. In-Order Traversal
3. Pre-Order Traversal
4. Post-Order Traversal
5. Removal
6. Exit
Enter your choice : 1
Enter Number to be inserted : 45
Binary Search Tree Operations
-----------------------------
1. Insertion/Creation
2. In-Order Traversal
3. Pre-Order Traversal
4. Post-Order Traversal
5. Removal
6. Exit
Enter your choice : 1
Enter Number to be inserted : 56
Binary Search Tree Operations
-----------------------------
1. Insertion/Creation
2. In-Order Traversal
3. Pre-Order Traversal
4. Post-Order Traversal
5. Removal
6. Exit
Enter your choice : 1
Enter Number to be inserted : 78
Binary Search Tree Operations
-----------------------------
1. Insertion/Creation
2. In-Order Traversal
3. Pre-Order Traversal
4. Post-Order Traversal
5. Removal
6. Exit
Enter your choice : 2
Display In-Order Traversal
-------------------
45 56 78
Binary Search Tree Operations
-----------------------------
1. Insertion/Creation
2. In-Order Traversal
3. Pre-Order Traversal
4. Post-Order Traversal
5. Removal
6. Exit
Enter your choice : 6
