HOME
/*PROGRAM
TO IMPLEMENT BINARY SEARCH TREE*/
#include<iostream.h>
#include<conio.h>
class
tree;
class
stack //CLASS
DECLARATION
{
tree* pointer;
stack *top;
public:
stack()
{
top=NULL;
}
void push(tree* i)
{
stack *p;
p= new stack;
p->pointer =i;
p->top = top;
top = p;
}
tree* pop()
{
tree* temp;
stack *tempp;
temp =
top->pointer;
tempp = top->top;
delete top;
top = tempp;
return temp;
}
int empty();
};
int
stack::empty()
{
if(top == NULL)
return 1;
return 0;
}
class
tree
{
int data;
tree* left;
tree* right;
public:
tree()
{
left = NULL;
right = NULL;
data =0;
}
void in_order()
{
stack s;
tree *p;
cout<<endl;
p = this;
while(p != NULL || !s.empty())
{
while( p!= NULL)
{
s.push(p);
p = p->left;
}
if(!s.empty())
{
p = s.pop();
cout<<p->data<<” “;
p = p->right;
}
}
}
void pre_order()
{
stack s;
tree *p;
cout<<endl;
s.push(this);
while(!s.empty())
{
p = s.pop();
while(p != NULL)
{
cout<<p->data<< ” “;
if(p->right != NULL)
s.push(p->right);
p = p->left;
}
}
}
void post_order()
{
stack s;
tree *p;
cout<<endl;
p = this;
while(1)
{
while( p != NULL)
{
p->data = -p->data;
s.push(p);
p = p->left;
}
if(s.empty())
return;
p = s.pop();
while(p->data > 0)
{
cout<<p->data<<” “;
if(s.empty())
return;
p= s.pop();
}
p->data = -p->data;
s.push(p);
p = p->right;
}
}
void deletion(int i)
{
int flag=0;
tree *p,*q;
p = this;
while( p!= NULL)
{
if(i < p->data)
{
q=p;
p= p->left;
}
else if(i > p->data)
{
q=p;
p=p->right;
}
else if(i== p->data)
{
flag=1;
break;
}
}
if(flag == 0)
{
cout<<endl<<i<<”
not in the list.
&nb
sp; &n
bsp;
no deletion performed.”;
return;
}
&nb
sp; // if deleting
element is root
if(i == data)
{
if(p->right == NULL)
{//replace
with in-order predecessor
int temp;
temp =p->left->max();
p->deletion(temp);
p->data = temp;
return;
}
else if(p->left == NULL)
{//replace
with in-order successor
int temp;
temp = p->right->min();
p->deletion(temp);
p->data = temp;
return;
}
}
// p has no
children.
if(p->right == NULL && p->left
== NULL)
{
if(q->right == p)
q->right = NULL;
else
q->left = NULL;
delete p;
}
//p has
only one child.
else if( p->right == NULL)
{
if(q->right == p)
q->right = p->left;
else
q->left = p->left;
delete p;
}
else if( p->left == NULL)
{
if(q->right == p)
q->right = p->right;
else
q->left = p->right;
delete p;
}
//p have
both children.
else
{
int temp;
temp = p->left->max();
p->deletion(temp);
p->data = temp;
}
}
int max()
{
tree *p = this;
while(p->right != NULL)
p = p->right;
return p->data;
}
int min()
{
tree *p = this;
while(p->left != NULL)
p = p->left;
return p->data;
}
void insert(int i)
{
if(data == 0)//null
tree checking
{
data = i;
return;
}
tree *p = this;
tree *q = this;
tree *temp;
while(p != NULL)
{
q = p;
if(i < p->data )
p = p->left;
else if(i > p->data)
p = p->right;
else
return;
}
temp = new tree;
temp->data = i;
if(i < q->data)
q->left = temp;
else
q->right = temp;
}
};
void
main()
{
tree t;
int i,n,num;
cout<<endl<<”ENTER
THE NO OF ELEMENTS
&nb
sp;
IN THE BINARY SEARCH TREE: “;
cin >>n;
cout<<”ENTER
THE ELEMENTS:\t”;
for(i=0; i<n; i++)
{
cin>>num;
t.insert(num);
}
cout<<”THE
ELEMENTS IN
&nb
sp;
THE INORDER TRAVERSAL”;
t.in_order();
cout<<”THE
ELEMENTS IN
THE POSTORDER TRAVERSAL\n”;
t.post_order();
cout<<”THE
ELEMENTS IN
THE PREORDER TRAVERSAL”;
t.pre_order();
cout<<”ENTER
THE
&nb
sp;
ELEMENT TO BE DELETE: “;
cin >>num;
t.deletion(num);
cout<<endl<<”AFTER
DELETION: “;
t.in_order();
}
//program ends
/* output:
ENTER
THE NO OF ELEMENTS IN THE BINARY SEARCH TREE: 5
ENTER
THE ELEMENTS: 1
45
2
67
9
THE
ELEMENTS IN THE INORDER TRAVERSAL
1
2 9 45 67
THE
ELEMENTS IN THE POSTORDER TRAVERSAL
9
2 67 45 1
THE
ELEMENTS IN THE PREORDER TRAVERSAL
1
45 2 9 67 ENTER THE ELEMENT TO BE DELETE: 1
AFTER
DELETION:
2
9 45 67 Press any key to continue
*/
