Hey Friends here is a simple C++ code for deleting a node from a binary tree.
Deletion.cpp:
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
typedef struct node
{
int d;
struct node *l;
struct node *r;
}tree;
void preorder(tree *);
void postorder(tree *);
void inorder(tree *);
void del(tree **,int);
tree *p,*l;
int check(tree *,int);
void main() {
tree *s,*t,*root=NULL;
char ch;
int n;
clrscr();
do {
cout<<"\nEnter the element:";
s=(tree *)malloc(sizeof(tree));
cin>>s->d;
s->l=NULL;
s->r=NULL;
if(root==NULL)
root=s;
else {
t=root;
while(1) {
if(t->d>s->d) {
if(t->l==NULL) {
t->l=s;
break;
}
t=t->l;
}
else {
if(t->r==NULL) {
t->r=s;
break;
}
t=t->>r;
}
}
}
cout<<"\nPress y/Y to enter another data:";
cin>>ch;
}while(ch=='Y'||ch=='y');
do {
cout<<"\nEnter your choice:";
cout<<"\n1.Preorder traversal";
cout<<"\n2.Inorder traversal";
cout<<"\n3.Postorder traversal";
cout<<"\n4.Delete a node";
cout<<"\n5.Stop\n";
cin>>n;
switch(n) {
case 1:cout<<"\nPreorder traversal is:";
preorder(root);
break;
case 2:cout<<"\nInorder traversal is:";
inorder(root);
break;
case 3:cout<<"\nPostorder traversal is:";
postorder(root);
break;
case 4:cout<<"\nEnter the element to be deleted:";
int d;
cin>>d;
del(&root,d);
break;
case 5:cout<<"\nThank you for visiting";
break;
default:cout<<"\nSorry wrong choice";
}
}while(n!=5);
getch();
}
void preorder(tree *n) {
if(n==NULL)
return;
cout<<"\t"<<n->d;
preorder(n->l);
preorder(n->r);
}
void inorder(tree *n) {
if(n==NULL)
return;
inorder(n->l);
cout<<"\t"<<n->d;
inorder(n->r);
}
void postorder(tree *n) {
if(n==NULL)
return;
postorder(n->l);
postorder(n->r);
cout<<"\t"<<n->d;
}
int check(tree *r,int n) {
p=l=r;
while(l) {
if(l->d==n)
return 1;
p=l;
if(l->d>n)
l=l->l;
else
l=l->r;
}
return 0;
}
void del(tree **r,int n) {
tree *s,*ps;
if(check(*r,n)) {
if(l->l==NULL&&l->r==NULL) {
if(p->r==l)
p->r=NULL;
else
p->l=NULL;
}
else if(l->l==NULL||l->r==NULL) {
if(p==l) {
if(l->l==NULL)
*r=l->r;
else
*r=l->l;
}
else if(p->r==l)
if(l->l==NULL)
p->r=l->r;
else
p->r=l->l;
else
if(l->l==NULL)
p->l=l->r;
else
p->l=l->l;
}
else {
ps=s=l->l;
while(s->r) {
ps=s;
s=s->r;
}
if(ps==s)
if(p->r==l)
p->r=s;
else
p->l=s;
else {
l->d=s->d;
l=s;
ps->r=l->l;
}
}
free(l);
cout<<"\nDeletion is successful and the resultant tree is:"<<endl;
preorder(*r);
}
else
cout<<"\nEntered element not found";
}
Have Fun....................
0 comments:
Post a Comment
Note: only a member of this blog may post a comment.