Click here to hide categories Click here to show left categories

User: Home          welcome : Guest          Log In / Register here     




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 3099 times
Author:
Rohit kakria
I am software developer
Related Articles:
Related Interview Questions: No related interview question