Binary Search Traversal C Program Data Structure

This Program is for Binary Search Tree and Traversal in C, and is part of Mumbai University MCA Colleges Data Structures in C program MCA Sem 2

# include <stdio.h>
#include<conio.h>
# include <malloc.h>

struct node
{
          int info;
          struct node *lchild;
          struct node *rchild;
}*root,*t;
struct node* search(struct node* ptr,int info);
void find(int item,struct node **par,struct node **loc);
void insert(int item);
void del(int item);
void case_a(struct node *par,struct node *loc );
void case_b(struct node *par,struct node *loc);
void case_c(struct node *par,struct node *loc);
void preorder(struct node *ptr);
void inorder(struct node *ptr);
void postorder(struct node *ptr);
void display(struct node *ptr,int level);
int item,n;

void main()
{
struct node *ptr;
int info;
          int choice,num;
          clrscr();
          root=NULL;
printf("\n\n============== BINARY SEARCH TREE ============\n\n");
          while(1)
          {
                   printf("\n\n------------- MAIN MENU --------------------\n\n");
                   printf("\n1.Insert\n\n");
                   printf("\n2.Delete\n\n");
                   printf("\n3.Inorder Traversal\n\n");
                   printf("\n4.Preorder Traversal\n\n");
                   printf("\n5.Postorder Traversal\n\n");
                   printf("\n6.Search\n\n");
                   printf("\n7.Display\n\n");
                   printf("\n8.Exit\n\n");
                   printf("\nEnter your choice : ");
                   scanf("%d",&choice);

                   switch(choice)
                   {
                    case 1:
printf("\n\n~~~~~~~~~~~~~~~ INSERTION ~~~~~~~~~~~~~~~~\n\n");
                             printf("\nEnter the number to be inserted : ");
                             scanf("%d",&num);
                             insert(num);
                             break;
                    case 2:
printf("\n\n~~~~~~~~~~~~~~~ DELETION ~~~~~~~~~~~~~~~~\n\n");
                             printf("\nEnter the number to be deleted : ");
                             scanf("%d",&num);
                             del(num);
                             break;
                    case 3:
printf("\n\n~~~~~~~~~~~~~~~ INORDER TRAVERSAL ~~~~~~~~~~~~~~~~\n\n");
                             inorder(root);
                             break;
                    case 4:
printf("\n\n~~~~~~~~~~~~~~~ PREORDER TRAVERSAL ~~~~~~~~~~~~~~~~\n\n");
                             preorder(root);
                             break;
                    case 5:
printf("\n\n~~~~~~~~~~~~~~~ POSTORDER TRAVERSAL ~~~~~~~~~~~~~~~~\n\n");
                             postorder(root);
                             break;

                    case 6:
printf("\n\n~~~~~~~~~~~~~~~ SEARCHING ~~~~~~~~~~~~~~~~\n\n");
                             printf("\nEnter the node to be searched :");
                             scanf("%d",&info);
                             ptr=search(ptr,info);
                             if(ptr==NULL)
                             {
                             printf("\n\n------------------------\n\n");
                             printf("\nSEARCH ELEMENT NOT FOUND");
                             printf("\n\n------------------------\n\n");
                             }
                             else
                             {
                             printf("\n\n------------------------\n\n");
                             printf("\nSEARCHED ELEMENT IS %d",ptr->info);
                             printf("\n\n------------------------\n\n");
                             }
                             break;
                    case 7:
printf("\n\n~~~~~~~~~~~~~~~ DISPLAYING ~~~~~~~~~~~~~~~~\n\n");
                             display(root,1);
                             break;
                    case 8:
                             exit();
                    default:
                             printf("\n\nINVALID ENTRY !!!!! TRY AGAIN\n\n");
                   }
          }
          getch();
}

void find(int item,struct node **par,struct node **loc)
{
          struct node *ptr,*ptrsave;

          if(root==NULL)
          {
                   *loc=NULL;
                   *par=NULL;
                   return;
          }
          if(item==root->info)
          {
                   *loc=root;
                   *par=NULL;
                   return;
          }
          if(item<root->info)
                   ptr=root->lchild;
          else
                   ptr=root->rchild;
          ptrsave=root;

          while(ptr!=NULL)
          {
                   if(item==ptr->info)
                   {       *loc=ptr;
                             *par=ptrsave;
                             return;
                   }
                   ptrsave=ptr;
                   if(item<ptr->info)
                             ptr=ptr->lchild;
                   else
                             ptr=ptr->rchild;
           }
           *loc=NULL;
           *par=ptrsave;
}

void insert(int item)
{       struct node *tmp,*parent,*location;
          find(item,&parent,&location);
          if(location!=NULL)
          {
                   printf("\n\n------------------------------\n\n");
                   printf("\nITEM ALREADY PRESENT");
                   printf("\n\n------------------------------\n\n");
                   return;
          }

          tmp=(struct node *)malloc(sizeof(struct node));
          tmp->info=item;
          tmp->lchild=NULL;
          tmp->rchild=NULL;

          if(parent==NULL)
                   root=tmp;
          else
                   if(item<parent->info)
                             parent->lchild=tmp;
                   else
                             parent->rchild=tmp;
}

void del(int item)
{
          struct node *parent,*location;
          if(root==NULL)
          {
                   printf("\n\n------------------------------\n\n");
                   printf("\nTREE IS EMPTY");
                   printf("\n\n------------------------------\n\n");
                   return;
          }

          find(item,&parent,&location);
          if(location==NULL)
          {
                   printf("\n\n------------------------------\n\n");
                   printf("\nITEM NOT PRESENT IN TREE");
                   printf("\n\n------------------------------\n\n");
                   return;
          }

          if(location->lchild==NULL && location->rchild==NULL)
                   case_a(parent,location);
          if(location->lchild!=NULL && location->rchild==NULL)
                   case_b(parent,location);
          if(location->lchild==NULL && location->rchild!=NULL)
                   case_b(parent,location);
          if(location->lchild!=NULL && location->rchild!=NULL)
                   case_c(parent,location);
          free(location);
}

void case_a(struct node *par,struct node *loc )
{
          if(par==NULL)
                   root=NULL;
          else
                   if(loc==par->lchild)
                             par->lchild=NULL;
                   else
                             par->rchild=NULL;
}

void case_b(struct node *par,struct node *loc)
{
          struct node *child;


          if(loc->lchild!=NULL)
                   child=loc->lchild;
          else
                   child=loc->rchild;

          if(par==NULL )
                   root=child;
          else
                   if( loc==par->lchild)
                             par->lchild=child;
                   else
                             par->rchild=child;
}

void case_c(struct node *par,struct node *loc)
{
          struct node *ptr,*ptrsave,*suc,*parsuc;

          ptrsave=loc;
          ptr=loc->rchild;
          while(ptr->lchild!=NULL)
          {
                   ptrsave=ptr;
                   ptr=ptr->lchild;
          }
          suc=ptr;
          parsuc=ptrsave;

          if(suc->lchild==NULL && suc->rchild==NULL)
                   case_a(parsuc,suc);
          else
                   case_b(parsuc,suc);

          if(par==NULL)
                   root=suc;
          else
                   if(loc==par->lchild)
                             par->lchild=suc;
                   else
                             par->rchild=suc;

          suc->lchild=loc->lchild;
          suc->rchild=loc->rchild;
}

void preorder(struct node *ptr)
{
          if(root==NULL)
          {
                   printf("\n\n----------------------------\n\n");
                   printf("\nTREE IS EMPTY");
                   printf("\n\n----------------------------\n\n");
                   return;
          }
          if(ptr!=NULL)
          {
                   printf("%d  ",ptr->info);
                   preorder(ptr->lchild);
                   preorder(ptr->rchild);
          }
}

void inorder(struct node *ptr)
{
          if(root==NULL)
          {
                   printf("\n\n----------------------------\n\n");
                   printf("\nTREE IS EMPTY");
                   printf("\n\n----------------------------\n\n");
                   return;
          }
          if(ptr!=NULL)
          {
                   inorder(ptr->lchild);
                   printf("%d  ",ptr->info);
                   inorder(ptr->rchild);
          }
}

void postorder(struct node *ptr)
{
          if(root==NULL)
          {
                   printf("\n\n----------------------------\n\n");
                   printf("\nTREE IS EMPTY");
                   printf("\n\n----------------------------\n\n");
                   return;
          }
          if(ptr!=NULL)
          {
                   postorder(ptr->lchild);
                   postorder(ptr->rchild);
                   printf("%d  ",ptr->info);
          }
}

void display(struct node *ptr,int level)
{
          int i;
          if ( ptr!=NULL )
          {
                   display(ptr->rchild, level+1);
                   printf("\n");
                   for (i = 0; i < level; i++)
                             printf("    ");
                   printf("%d", ptr->info);
                   display(ptr->lchild, level+1);
          }

}

struct node* search(struct node *ptr,int info)
{
if(ptr!=NULL)
          if(info< ptr->info)
                   ptr=search(ptr->lchild,info);
          else if(info > ptr->info)
                   ptr=search(ptr->rchild,info);
          return(ptr);

}




Hope this Program is useful to you in some sense or other. Keep on following this blog for more Mumbai University MCA College Programs. Happy Programming and Studying.

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)