Binary Search Tree

				
//**************************************
// Name: Binary Search Tree
// Description:Binary Search Tree (BST)
Add nodes to BST
Show BST in Pre-Order
Show BST in Post-Order
Show BST in In-Order
Search Binar search tree
Delete a Node from BST
Empty BST
// By: Salman Aziz
//
//This code is copyrighted and has// limited warranties.Please see http://www.Planet-Source-Code.com/vb/scripts/ShowCode.asp?txtCodeId=5500&lngWId=10//for details.//**************************************

#include <iostream>
using namespace std;
struct node
 { 
	 int value;// any digit
 node *right;// Pointer to right node
	 node *left;// Pointer to left node
	 node *parent; // Pointer to parent node value
 };
node *start_ptr = NULL;
node *current;		 // Used to move along the list
node *D;
int option = 0;
int name2;		//to hold digit to be deleted value 
void add_node_in_BST()
 { node *temp, *temp2;// Temporary pointers
 // Reserve space for new node and fill it with data
 temp = new node;
 cout << "Please enter any Digit: " << endl;
	 cin >> temp->value;
	 temp->left = NULL;
	 temp ->right=NULL;
	 temp->parent = NULL;
 // Set up link to start parent node
 if (start_ptr == NULL)
{ 
			 start_ptr = temp;
			 current = temp;
}
 else
{ 
		temp2 = start_ptr;
		while(temp->parent == NULL)
		{
				if(temp->value <= temp2->value) //current value is less then start value
				{
					if(temp2->left == NULL)
					{
						temp2->left = temp;
						temp->parent = temp2;
					}
					else
					{
						temp2 = temp2->left;
					}
				}
				if(temp->value > temp2->value) //current value is less then start value
				{
					if(temp2->right == NULL)
					{
						temp2->right = temp;
						temp->parent = temp2;
					}
					else
					{
						temp2 = temp2->right;
					}
				}
		}
		 current = temp;
}
 }
void display_BST_Pre(node *H)
 { 
		if(H!=NULL)
		{
			
		if(current != H)
		cout<<"Element is : "<<H->value<<endl;
		if(current == H)
		cout<<"Element is : "<<H->value<<"<---- Curent State"<<endl;
		display_BST_Pre(H->left);
		display_BST_Pre(H->right);
		}
	
 }
void display_BST_Post(node *H)
 { 
		if(H!=NULL)
		{
		display_BST_Post(H->left);
		display_BST_Post(H->right);
		if(current != H)
		cout<<"Element is : "<<H->value<<endl;
		if(current == H)
		cout<<"Element is : "<<H->value<<"<---- Curent State"<<endl;
		}
 }
void display_BST_In(node *H)
 { 
		if(H!=NULL)
		{
		 
		display_BST_In(H->left);
		if(current != H)
		cout<<"Element is : "<<H->value<<endl;
		if(current == H)
		cout<<"Element is : "<<H->value<<"<---- Curent State"<<endl;
		display_BST_In(H->right);
		}
	
 }
 void delete_node(int x)
 {
	node *ss;
	node *tp;
	ss = start_ptr;
	int f =0;
	int p = 0;
	while(ss != NULL)
	{
			if(ss->value == x)
			{
				f=1;
				if(p ==1)//go Left
				{
					if(ss->right == NULL && ss->left ==NULL)
					ss = NULL;
					if(ss->right == NULL && ss->left != NULL)
					ss = ss ->left;
					if(ss->right != NULL && ss->left == NULL)
					ss = ss ->right;
					if(ss->right != NULL && ss->left != NULL)
					{
						tp = ss;
						while(ss ->right != NULL)
						ss=ss->right;
						tp = tp ->parent;
						tp->left = ss;
						ss =ss->parent;
						ss ->right = NULL;
					}
				}
					
				if(p ==2)//Go Right
				{
					if(ss->right == NULL && ss->left ==NULL)
					ss = NULL;
					if(ss->right == NULL && ss->left != NULL)
					ss = ss ->left;
					if(ss->right != NULL && ss->left == NULL)
					ss = ss ->right;
					if(ss->right != NULL && ss->left != NULL)
					{
						tp = ss;
						ss = ss->left;
						while(ss ->right != NULL)
							ss=ss->right;
						tp = tp ->parent;
						tp->right = ss;
						ss =ss->parent;
						ss ->left = NULL;
					}
				}
						 
			}
			if(x < ss->value)//Go Left
			{
				ss= ss->left;
				p = 1;
			}
			else //Go Right
			{
				ss = ss->right;
				p = 2;
			}
	}
 }
int search(void)
 {		int x;
		int f=0;
		cout<<"Please Enter Value to search in BST"<<endl;
		cin>>x;
		node *S;
		S=start_ptr;
		while(S != NULL)
		{
			if(S->value == x)
			{
				f=1;
			}
			if(x < S->value)
			{
				S= S->left;
			}
			else 
			{
				S = S->right;
			}
		}
		return f;
 }
void main()
 { 
	 
	 int h;
	 int k;
	start_ptr = NULL;
do
	{
		cout << endl;
		cout << "0. Exit." << endl;
		cout << "1. Add nodes to BST." << endl;
		cout << "2. Show BST in Pre-Order." << endl;
		cout << "3. Show BST in Post-Order." << endl;
		cout << "4. Show BST in In-Order." << endl;
		cout << "5. Search Binar search tree." << endl;
		cout<<"6. Delete a Node from BST."<<endl;
		cout<<"7. Empty BST"<<endl;
		cout<<endl;
		cout<<"Enter your Choice:"<<endl;
cin >> option;
	 switch (option)
	{
	 case 1 : 
			 cout<<"Please Enter amount of node you want to add"<<endl;
			 cin>>h;
			 for(int i =0;i<h;i++)
			 add_node_in_BST(); 
 break;
		 case 3 :
			 D = start_ptr;
			 if(D != NULL)
			 {
			 cout<<"Result in Post-Order:"<<endl;
			 display_BST_Post(D);
			 }
			 else
				 cout<<endl<<"Your BST is Empty..!"<<endl;
			 break;
		case 2 :
			 D = start_ptr;
			 if(D != NULL)
			 {
			 cout<<"Result in Pre-Order:"<<endl;
			 display_BST_Pre(D);
			 }
			 else
				 cout<<endl<<"Your BST is Empty..!"<<endl;
			 break;
		case 4 :
			 D = start_ptr;
			 if(D != NULL)
			 {
			 cout<<"Result in In-Order:"<<endl;
			 display_BST_In(D);
			 }
			 else
				 cout<<endl<<"Your BST is Empty..!"<<endl;
			 break;
			
		 case 5 :
			k = search();
			if(k==1)
			 cout<<"Value Found.."<<endl;
			if(k==0)
			 cout<<"Value Not Fount.."<<endl;
			break;
			
		 case 6 :
			 cout<<"Please Enter Node Value.."<<endl;
			 cin>>h;
			 delete_node(h);
		 case 7 :
			 start_ptr = NULL;
			 cout<<"BST is now Empty"<<endl;
			 break;
	}
	}
 while (option != 0);
 }