Saturday, 9 August 2014

The various functions on BST

Now this length program is the Insertion, Deletion , Traversal, etc of the Binary Search Tree. If you have doubts, please let me know.
#include<stdio.h>
#include<stdlib.h>
#define max(A,B) (((A)>(B))?(A):(B))
struct node
{
        int data;
        struct node *rc,*lc;
}*newn,*ptr=NULL,*pre=NULL,*root=NULL,*succ=NULL;
void ins(int);
void del(int);
void inorder(struct node *temp);
void preorder(struct node *temp);
void postorder(struct node *temp);
void display(struct node*);
int height(struct node*);

main()
{
        int ch,r,x,h,l,d;
        do
        {
        printf("\nMenu:\n1.Isertion\n2.Deletion\n3.Traversal\n4.Level\n5.Height\n6.Display\n7.Exit\n");
        printf("\nEnter your choice:");
        scanf("%d",&ch);
        switch(ch)
        {
        case 1:
                printf("Enter the element to be inserted:");
                scanf("%d",&d);
                scanf("%d",&d);
                ins(d);
                break;
        case 2:
                printf("Enter the element to be deleted:");
                scanf("%d",&x);
                del(x);
                break;
        case 3: display(root);
                break;
        case 4:
                h=height(root);
                l=h-1;
                printf("\nLEVEL:%d",l);
                break;
        case 5:h=height(root);
                printf("\nHEIGHT:%d",h);
                break;
        case 6:
                display(root);
                break;
        case 7:break;
        default:
                printf("\nWrong choice\n");
                break;
        }
        }while(ch!=7);
}
void ins(int d)
{
        int flag=0;
         ptr=root;
         newn=(struct node*)malloc(sizeof(struct node));
        newn->data=d;
        newn->lc=NULL;
        newn->rc=NULL;
        while((ptr!=NULL)&&(flag==0))
        {
                if(d<ptr->data)
                {
                        pre=ptr;
                        ptr=ptr->lc;
                }
                else if(d>ptr->data)
                {
                        pre=ptr;
                        ptr=ptr->rc;
                }
                else
                {
                        flag=1;
                        printf("Element already exists!");
                }
        }
        if(ptr==NULL)
        {
           if(root==NULL)
           {
            root=newn;
            ptr=root;
           }
           else if(pre->data<d)
           {
             pre->rc=newn;
             ptr=pre->rc;
           }
           else if(pre->data>d)
           {
             pre->lc=newn;
             ptr=pre->lc;
           }
        }

}

void del(int x)
{
        ptr=root;
        while(ptr!=NULL)
        {
                if(x<ptr->data)
                {
                        pre=ptr;
                        ptr=ptr->lc;
                }
                else if(x>ptr->data)
                {
                        pre=ptr;
                        ptr=ptr->rc;
                }
                else if(ptr->data==x)
                {
                        if((ptr->lc==NULL)&&(ptr->rc==NULL))
                        {
                                if(root==ptr)
                                {
                                 free(root);
                                 root=NULL;
                                 break;
                                }
                                else if(pre->lc==ptr)
                                        pre->lc=NULL;
                                else if(pre->rc==ptr)
                                        pre->rc=NULL;
                                free(ptr);
                            break;

                        }

                        else if(ptr->lc!=NULL&&ptr->rc==NULL)
                        {
                        if(pre->lc==ptr)
                                pre->lc=ptr->lc;
                        else if(pre->rc==ptr)
                                pre->rc=ptr->lc;
                        free(ptr);
                        break;
                        }
                        else if(ptr->lc==NULL&&ptr->rc!=NULL)
                        {
                        if(pre->lc==ptr)
                                pre->lc=ptr->rc;
                        else if(pre->rc==ptr)
                                pre->rc=ptr->rc;
                        free(ptr);
                        break;
                        }
                        else if(ptr->lc!=NULL&&ptr->rc!=NULL)
                        {
                        succ=ptr->rc;
                        if(succ->lc==NULL)
                        {
                                if(ptr==root)
                                {
                                   succ->lc=root->lc;
                                  root=succ;
                                }
                                else if(pre->lc==ptr)
                                {
                                        pre->lc=succ;
                                        succ->lc=ptr->lc;
                                }
                                else if(pre->rc==ptr)
                                {
                                        pre->rc=succ;
                                        succ->rc=ptr->rc;
                                }
                                free(ptr);
                                break;
                        }
                        else
                        {
                                while(succ->lc!=NULL)
                                {
                                        pre=succ;
                                        succ=succ->lc;
                                }
                                ptr->data=succ->data;
                                pre->lc=succ->rc;
                                free(ptr);
                                break;
                                }
                        }
                }
        }
        if(ptr==NULL)
                {
                        printf("\nElement absent\n");
                }
}
void postorder(struct node *temp)
{
        if(temp!=NULL)
        {
                postorder(temp->lc);
                postorder(temp->rc);
                printf("  %d",temp->data);
        }
  }
 void preorder(struct node *temp)
{

        if(temp!=NULL)
        {
                printf("  %d",temp->data);
                preorder(temp->lc);
        preorder(temp->rc);
        }
}

void display(struct node *root1)
{
int i;
if(root1==NULL)
        printf("Empty tree!");
else
{
printf("\nEnter the order\n1:inorder\n2:preorder\n3:postorder\n");
         printf("\nEnter your choice:");
         scanf("%d",&i);
         if(i==1)
         {
                 printf("\nINORDER:\n");
         inorder(root1);

          }
         else if(i==2)
         {
         printf("\nPREORDER:\n");
         preorder(root1);
         }
         else
         {
                 printf("\nPOSTORDER:\n");
                 postorder(root1);
         }
}
}
 void inorder(struct node *temp)
{
        if(temp!=NULL)
        {
        inorder(temp->lc);
                printf("  %d",temp->data);
                inorder(temp->rc);
        }
}

int height(struct node *root)
{
        if(root==NULL)
                return 0;
        else
             return max(height(root->lc),height(root->rc));
}

No comments:

Post a Comment