SEARCH ADT-BINARY SEARCH TREE

AIM:
To Write a Program to implement the Binary Search Tree and perform insertion, deletion, searching, display of tree.




ALGORITHM:
1.CREATION:
STEP 1 :Read the value for the node which is to be created and store it in a node 
called New.
STEP 2 : Initially if(root!=NULL)then root=New
STEP 3 : Again read the next value of node created in New
STEP 4 :If(New->value<root->value)then attach new node as a left child of root   
otherwise attach New node as a right child of root
STEP 5 :Repeat step 3 and 4 for constructing required binary search tree completely. 


2.SEARCH:
STEP 1 :Get the Data for searching 
STEP 2 :If(root==NULL) terminate the search operation 
STEP 3 :Else Compare the root data with the new data
(i) If(root==New data)print data
(ii)If(root<New data)Consider the right child of the root node as the  root node and check for the three conditions again.
(iii) If(root>New data)Consider the left child of the root node as the  root node and check for the three conditions again.
3.DELETE:

STEP 1 :Search the parent of the leaf node and make the link to the leaf node
as NULL
STEP 2 :Search the parent of the node to be deleted with only one child
STEP 3 :.Assign the link of the parent node to the child of the node to be
deleted
STEP 4 :Search the parent of the node to be deleted with two children. Copy
the content of the in order successor to the node to be deleted.
STEP 5 :Release the memory for the deleted node.
4.DISPLAY:
STEP 1:To display the information in a binary search tree traverse a binary 
search tree in the form of traversing order. 
PROGRAM:

#include<iostream.h>
#include<conio.h>
class bintree
{
typedef struct bst
{
int data;
struct bst*left,*right;
}
node;
node *root,*New,*temp,*parent;
public:
bintree()
{
root=NULL;
}
void create();
void display();
void delet(); void find();
void insert(node *,node *);
void inorder(node *);
void search(node **,int,node**);
void del(node *,int);
};
void bintree::create()
{
New=new node;
New->left=NULL;
New->right=NULL;
cout<<"\n Enter the element";
.;cin>>New->data;
if(root==NULL)
root=New;
else
insert(root,New);
}
void bintree::insert(node *root,node *New)
{
if(New->data<root->data)
{
if(root->left==NULL)
root->left=New;
else
insert(root->left,New);
}
if(New->data>root->data)
{
if(root->right==NULL)
root->right=New;
else
insert(root->right,New);
}
}
void bintree::display()
{
if(root==NULL)
cout<<"Tree is Not Created";
else
{
cout<<"\n The Tree is:";
inorder(root);
}
}
void bintree::inorder(node *temp)
{
if(temp!=NULL)
{
inorder(temp->left);
cout<<" "<<temp->data;
inorder(temp->right);
}
}
void bintree::find()
{
int key;
cout<<"\n Enter the element which you want to search";
cin>>key;
temp=root;
search(&temp,key,&parent);
if(temp==NULL)
cout<<"\n Element is not present";
else
cout<<"\n Parent of node"<<temp->data<<"is"<<parent->data;
}
void bintree::search(node **temp,int key,node **parent)
{
if(*temp==NULL)
cout<<endl<<"Tree is Not Created"<<endl;
else
{
while(*temp!=NULL)
{
if((*temp)->data==key)
{
cout<<"\n The"<<(*temp)->data<<"Element is present";
break;
}
*parent=*temp;
if((*temp)->data>key) *temp=(*temp)->left;
else
*temp=(*temp)->right;
}
}
return;
}
void bintree::delet()
{
int key;
cout<<"\n Enter The Element U wish to Delete";
cin>>key;
if(key==root->data)
{
bintree();
}
else
del(root,key);
}
void bintree::del(node *root,int key)
{
node *temp_succ;
if(root==NULL)
cout<<"Tree is not Created";
else
{
temp=root;
search(&temp,key,&parent);
if(temp->left!=NULL&&temp->right!=NULL)
{
parent=temp;
temp_succ=temp->right;
while(temp_succ->left!=NULL)
{
parent=temp_succ;
temp_succ=temp_succ->left;
}
temp->data=temp_succ->data;
temp->right=NULL;
cout<<"Now Deleted it!";
return;
}
if(temp->left!=NULL&&temp->right==NULL)
{
if(parent->left==temp)
parent->left=temp->left;
else
parent->right=temp->left;
temp=NULL;
delete temp;
cout<<"Now Deleted it!";
return;
}if(temp->left==NULL&&temp->right!=NULL)
{
if(parent->left==temp)
parent->left=temp->right;
else
parent->right=NULL;
cout<<"Now Deleted it!";
return;
}
}
}
void main()
{
int choice;
char ans='N';
bintree tr;
cout<<"\n\t Program for binary search tree";
do
{
cout<<"\n 1.Create\n 2.Search\n 3.Delete \n 4.Display";
cout<<"\n\n Enter your choice:";
cin>>choice;
switch(choice)
{
case 1:do
{
tr.create();
cout<<"Do u want to enter more elements?(y/n)"<<endl;
ans=getch();
}
while(ans=='y');
break;
case 2:tr.find();
break;
case 3:tr.delet();
break;
case 4:tr.display();
break;
}
}
while(choice!=5);
}

OUTPUT:
Program For Binary Search Tree
1.  Create
2.  Search
3.  Delete
4.  Display
Enter your choice : 1
Enter The Element  : 10
Do you Want To enter More elements?(y/n) y
Enter The Element  : 8  
Do you Want To enter More elements?(y/n) y
Enter The Element  : 7
Do you Want To enter More elements?(y/n) y
Enter The Element  : 9
Do you Want To enter More elements?(y/n) y
Enter The Element  : 12
Do you Want To enter More elements?(y/n) n
Enter your choice : 4
The Tree is :  7  8
Enter your choice :  2 9 10  12
Enter The Element Which You Want To Search : 10 The 10 Element is Present
Parent of node 10 is 9 Enter your choice : 3
Enter The Element U wish to Delete : 10
The 10 Element is Present Now Deleted it!
Enter your choice : 4 
The Tree is : 7  8

Enter your choice : 5  9  12