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.