The following is a link list implementation of BST I found on net,
I have made some changes to it if you found any error inform me I will fix it.
#include
using namespace std;
class BinarySearchTree
{
private:
struct tree_node
{
tree_node* left;
tree_node* right;
int data;
};
tree_node* root;
public:
BinarySearchTree()
{
root = NULL;
}
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)
{
tree_node* temp = new tree_node;
tree_node* parent;
temp->data = d;
temp->left = NULL;
temp->right = NULL;
parent = NULL;
// is this a new tree?
if(isEmpty()) root = temp;
else
{
//Note: ALL insertions are as leaf nodes
tree_node* current;
current = root;
// Find the Node's parent
while(current)
{
parent = current;
if(temp->data > current->data) current = current->right;
else current = current->left;
}
if(temp->data < parent->data)
parent->left = temp;
else
parent->right = temp;
}
}
void BinarySearchTree::remove(int d)
{
//Locate the element
bool found = false;
if(isEmpty())
{
cout<<" This Tree is empty! "<
return;
}
tree_node* current;
tree_node* parent;
current = root;
while(current != NULL)
{
if(current->data == d)
{
found = true;
break;
}
else
{
parent = current;
if(d>current->data) current = current->right;
else current = current->left;
}
}
if(!found)
{
cout<<" Data not found! "<<"\n";
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((current->left == NULL && current->right != NULL) || (current->left != NULL && current->right == NULL))
{
if(current->left == NULL && current->right != NULL)// right child present, no left child
{
if(parent->left == current)
{
parent->left = current->right;
delete current;
}
else
{
parent->right = current->right;
delete current;
}
}
else // left child present, no right child
{
if(parent->left == current)
{
parent->left = current->left;
delete current;
}
else
{
parent->right = current->left;
delete current;
}
}
return;
}
if( current->left == NULL && current->right == NULL) //We're looking at a leaf node
{
if(parent->left == current) parent->left = NULL;
else parent->right = NULL;
delete current;
return;
}
//Node with 2 children
// replace node with smallest value in right subtree
if (current->left != NULL && current->right != NULL)
{
tree_node* chkright;
chkright = current->right;
if((chkright->left == NULL) && (chkright->right == NULL))
{
current->data = chkright->data;
delete chkright;
current->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((current->right)->left != NULL)
{
tree_node* leftcurr;
tree_node* leftcurrp;
leftcurrp = current->right;
leftcurr = (current->right)->left;
while(leftcurr->left != NULL)
{
leftcurrp = leftcurr;
leftcurr = leftcurr->left;
}
current->data = leftcurr->data;
delete leftcurr;
leftcurrp->left = NULL;
}
else
{
tree_node* temp;
temp = current;
current = current->right;
delete temp;
}
}
return;
}
}
void BinarySearchTree::print_inorder()
{
inorder(root);
}
void BinarySearchTree::inorder(tree_node* p)
{
if(p != NULL)
{
if(p->left) inorder(p->left);
cout<<" "<data<<" ";
if(p->right) inorder(p->right);
}
else return;
}
void BinarySearchTree::print_preorder()
{
preorder(root);
}
void BinarySearchTree::preorder(tree_node* p)
{
if(p != NULL)
{
cout<<" "<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)
{
if(p != NULL)
{
if(p->left) postorder(p->left);
if(p->right) postorder(p->right);
cout<<" "<data<<" ";
}
else return;
}
int main()
{
BinarySearchTree b;
int ch,tmp,tmp1;
do
{
cout< cout<<" Binary Search Tree Operations "<<"\n";
cout<<" ----------------------------- "<<"\n";
cout<<" 1. Insertion/Creation "<<"\n";
cout<<" 2. In-Order Traversal "<<"\n";
cout<<" 3. Pre-Order Traversal "<<"\n";
cout<<" 4. Post-Order Traversal "<<"\n";
cout<<" 5. Removal "<<"\n";
cout<<" 6. Exit "<<"\n";
cout<<" Enter your choice : ";
cin>>ch;
switch(ch)
{
case 1 : cout<<" Enter Number to be inserted : ";
cin>>tmp;
b.insert(tmp);
break;
case 2 : cout< cout<<" In-Order Traversal "<<"\n";
cout<<" -------------------"<<"\n";
b.print_inorder();
break;
case 3 : cout< cout<<" Pre-Order Traversal "<<"\n";
cout<<" -------------------"<<"\n";
b.print_preorder();
break;
case 4 : cout< cout<<" Post-Order Traversal "<<"\n";
cout<<" --------------------"<<"\n";
b.print_postorder();
break;
case 5 : cout<<" Enter data to be deleted : ";
cin>>tmp1;
b.remove(tmp1);
break;
case 6 : cout<<"Exiting";
return 0;
break;
default : cout<<"Enter valid choice";
break;
}
}while(ch!=6);
}
