Wednesday, March 12, 2014

BINARY SEARCH TREE in C++

Binary search tree has one data variable and two pointer pointing to child.

structure of binary search tree can be represented like this.

 
                                                 



#include<iostream>
using namespace std;
struct bst
{
bst *lc;
int data;
bst *rc;
};
int findmin(bst *t)
{
if(t->lc==NULL)
return t->data;
else
{
return findmin(t->lc);
}

}
void insert(bst *&t, int k)
{
if(t==NULL)
{
t=new bst;
t->data=k;
t->lc=NULL;
t->rc=NULL;
}
else if(k>t->data)
{
insert(t->rc,k);
}
else
{
insert(t->lc,k);
}
}
 void del(bst *&t,int k)
{
int c;

if(k>t->data)
{
del(t->rc,k);
}
else if(k<t->data)
{
del(t->lc,k);
}
else
{
if(t->lc==NULL&&t->rc==NULL)
t=NULL;
else if(t->lc==NULL&&t->rc!=NULL)
{
t=t->rc;
}
else if(t->lc!=NULL&t->rc==NULL)
{
int c=findmin(t->lc);
t->data=c;
del(t->lc,c);
}
else if(t->lc!=NULL&t->rc!=NULL)
{
int c=findmin(t);
t->data=c;
del(t->lc,c);
}
}
}
void max(bstnode *t)
{
while(t->rchild!=NULL)
t=t->rchild;cout<<"\nmaximum is\n"<<t->data;

}
void min(bstnode *t)
{
while(t->lchild!=NULL)
t=t->lchild;cout<<"\nminimum is\n"<<t->data;
}
void printleaf(bstnode *t)
{
if(t->lchild==NULL&&t->rchild==NULL)
cout<<t->data;
if(t->lchild!=NULL)
printleaf(t->lchild);
if(t->rchild!=NULL)
printleaf(t->rchild);
}
void show(bst *t)
{
if(t!=NULL)
{
show(t->lc);
cout<<t->data<<" ";
show(t->rc);
}
}
int main()
{
int k;
bst *t;
t=NULL;
cout<<"enter ";
cin>>k;
while(k!=-1)
{
insert(t,k);
cin>>k;
}
show(t);
cout<<"\nenter the node you want to delete";
cin>>k;
del(t,k);
show(t);

}

No comments:

Post a Comment

Contributors

Translate