Deleting from Binary search tree implementation in C++
|
|
|
Download Attachment
|
#include < iostream.h>
#include < conio.h>
#include < malloc.h>
struct tree
{
struct tree *left;
int info;
struct tree *right;
}*root,*ptr,*newnode,*par,*stack[100],*child;
int loc=0;
void create();
void find(int);
void traverse();
void del(int);
void main()
{
int i,item;
clrscr();
for(i=0;i<5;i++)
{
create();
}
cout<<"\nEnter the item you want to delete from tree: ";
cin>>item;
del(item);
}
void create()
{
int item;
cout<<"\nEnter the info: ";
cin>>item;
find(item);
if(loc==1)
{
traverse();
}
else
{
newnode=(struct tree*)malloc(sizeof(struct tree));
newnode->info=item;
newnode->left=NULL;
newnode->right=NULL;
if(par==NULL)
{
root=newnode;
}
else if(iteminfo)
{
par->left=newnode;
}
else
{
par->right=newnode;
}
traverse();
}
}
void del(int item)
{
struct tree *save,*suc,*parsuc,*temp;
find(item);
if(loc==0)
{
cout<<"\nItem is not in the tree";
traverse();
}
else
{
if((ptr->right!=NULL)&&(ptr->left!=NULL))
{
temp=ptr->right;
save=ptr;
while(temp->left!=NULL)
{
save=temp;
temp=temp->left;
}
suc=temp;
parsuc=save;
//ptr=suc;
//par=parsuc;
if((temp->left==NULL)&&(temp->right==NULL))
{
child=NULL;
}
else if(temp->left!=NULL)
{
child=temp->left;
}
else
{
child=temp->right;
}
if(parsuc!=NULL)
{
if(temp==parsuc->left)
{
parsuc->left=child;
}
else
{
parsuc->right=child;
}
}
else
{
root=child;
}
if(par!=NULL)
{
if(ptr==par->left)
{
par->left=suc;
}
else
{
par->right=suc;
}
}
else
{
root=suc;
}
suc->left=ptr->left;
suc->right=ptr->right;
}
else
{
if((ptr->left==NULL)&&(ptr->right==NULL))
{
child=NULL;
}
else if(ptr->left!=NULL)
{
child=ptr->left;
}
else
{
child=ptr->right;
}
if(par!=NULL)
{
if(ptr==par->left)
{
par->left=child;
}
else
{
par->right=child;
}
}
else
{
root=child;
}
}
cout<<"\nAfter deletion tree is:\n";
traverse();
}
}
void find(int item)
{
struct tree *save;
if(root==NULL)
{
loc=0;
par=NULL;
return;
}
else if(item==root->info)
{
loc=1;
ptr=root;
par=NULL;
return;
}
else if(iteminfo)
{
ptr=root->left;
save=root;
}
else
{
ptr=root->right;
save=root;
}
while(ptr!=NULL)
{
if(item==ptr->info)
{
loc=1;
par=save;
return;
}
else if(iteminfo)
{
save=ptr;
ptr=ptr->left;
}
else
{
save=ptr;
ptr=ptr->right;
}
}
loc=0;
par=save;
}
void traverse()
{
int top=0;
stack[0]=NULL;
ptr=root;
cout<<"\nTree is:\n";
while(ptr!=NULL)
{
cout<info<<" ";
if(ptr->right!=NULL)
{
top=top+1;
stack[top]=ptr->right;
}
if(ptr->left!=NULL)
{
ptr=ptr->left;
}
else
{
ptr=stack[top];
top=top-1;
}
}
getch();
}
|
|
|
|
|
|
|
|
|
|
Share this article
| Print |
Article read by 3064 times
|
|
|
|