Algorithm for insertion & deletion of elements in a binary search tree
--------------------------------------------------------------------------------------------------------------------------------
Step 1- start
Step 2-create an object for the class BINTREE
Step 3- DO the following….
a) Print the Options
b) Read the choice
Step 4-
A) If the choice is “insertion” then
a.1) read the element to be Inserted
a.1) call the member function INSERT with the obj.
a.3) Return
B) if the choice is “deletion” then
b.1) Read the element to be Deleted
b.2) call the member function “delete” with obj
b.3) display the pointer location as “deleted Item Location” & RETURN
C) if the choice is”DISPLAY” then
c.1)call the member function “display” with the class obj. & RETURN
D) If the choice is “EXIT” then
D1) display Bye
UNTIL the choice is not "EXIT"
Step 5- STOP
------------------------------------------------------------------------------------------------------------------------------------
FLOW CHARTs
-----------------------------------------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------------------------------------------
C++ IMPLEMENTATION
------------------------------------------------------------------------------------------------------------------------------------
//program for INSERTION & DELETION ON BINARY TREE -
#include<iostream.h>
#include<conio.h>
//----------------------FUNCTION DECLARATION--------------
void insert(int,int );
void delte(int);
void display(int);
int search(int);
int search1(int,int);
int tree[10],t=1,s,x,i;
//------------------MAIN FUNCTION---------------------
void main()
{
clrscr();
int ch,y;
for(i=1;i<10;i++)
tree[i]=-1;
cout<<"\n\t BINARY TREE INSERTION & DELETION \n\n";
do
{
cout <<"1.INSERT\n2.DELETE\n3.DISPLAY\n4.SEARCH\n5.EXIT\nEnter your choice:\n";
cin >> ch;
switch(ch)
{
case 1:
cout <<"\nEnter the element to insert";
cin >> ch;
insert(1,ch);
break;
case 2:
cout <<"\nEnter the element to delete\n";
cin >>x;
y=search(1);
if(y!=-1)
{
delte(y);
cout<<"\n"<<y<<" ELEMENT IS DELETED\n";
}
else
cout<<"\nNo such element in tree\n";
break;
case 3:
display(1);
cout<<"\n";
for(int i=0;i<=10;i++)
cout <<i<<endl;
cout <<"\n";
break;
case 4:
cout <<"\nEnter the element to search:\n";
cin >> x;
y=search(1);
if(y == -1) cout <<"\nNo such element in tree\n";
else cout <<x << " is in " <<y <<" position\n";
break;
case 5:
cout<<"\nBYE...!";
getch();
break;
}
}
while(ch!=5);
}
//------------------function DEFINITION---------------------------
void insert(int s,int ch )
{
int x;
if(t==1)
{
tree[t++]=ch;
return;
}
x=search1(s,ch);
if(tree[x]>ch)
tree[2*x]=ch;
else
tree[2*x+1]=ch;
t++;
}
//-----------------------FUNCTION DEFINITION FOR DELETION--------
void delte(int x)
{
if( tree[2*x]==-1 && tree[2*x+1]==-1)
tree[x]=-1;
else if(tree[2*x]==-1)
{ tree[x]=tree[2*x+1];
tree[2*x+1]=-1;
}
else if(tree[2*x+1]==-1)
{ tree[x]=tree[2*x];
tree[2*x]=-1;
}
else
{
tree[x]=tree[2*x];
delte(2*x);
}
t--;
}
//------SEARCHING AN ELEMENT IN TREE------------
int search(int s)
{
if(t==1)
{
cout <<"no element in tree";
return -1;
}
if(tree[s]==-1)
return tree[s];
if(tree[s]>x)
search(2*s);
else if(tree[s]<x)
search(2*s+1);
else
return s;
}
//-----------------DISPLAY FUNCTION DEFINITION------------------
void display(int s)
{
if(t==1)
{cout <<"\n No element in tree:\n";
return;}
for(int i=1;i<10;i++)
if(tree[i]==-1)
cout <<" ";
else cout <<tree[i]<<endl;
return ;
}
int search1(int s,int ch)
{
if(t==1)
{
cout <<"\nNo element in tree\n";
return -1;
}
if(tree[s]==-1)
return s/2;
if(tree[s] > ch)
search1(2*s,ch);
else search1(2*s+1,ch);
}
OUTPUT:
1.INSERT
2.DELETE
3.DISPLAY
4.SEARCH
5.EXIT
Enter your choice:3
no element in tree:
0
1
2
3
4
5
6
7
8
9
1.INSERT
2.DELETE
3.DISPLAY
4.SEARCH
5.EXIT
Enter your choice:1
Enter the element to insert 10
1.INSERT
2.DELETE
3.DISPLAY
4.SEARCH
5.EXIT
Enter your choice:4
Enter the element to search: 10
10 is in 1 position
1.INSERT
2.DELETE
3.DISPLAY
4.SEARCH
5.EXIT
Enter your choice:5
Bye..!
No comments:
Post a Comment