Perform Tree Operations - insert, traversal, preorder,post order and in order

/* Program Tree Operation insert traversal preorder,post order,inorder*/



#include<stdio.h>


#include<alloc.h>


#include<conio.h>


#include<stdio.h>


struct tree
{

 int info;


 struct tree *left;


 struct tree *right;


};



struct tree *insert(struct tree *,int);

void inorder(struct tree *);


void postorder(struct tree *);


void preorder(struct tree *);


struct tree *delet(struct tree *,int);


struct tree *search(struct tree *);


int main(void)

{



struct tree *root;

 int choice, item,item_no;
 root = NULL;

 clrscr();
/* rear  = NULL;*/

 do
 {

  do


  {
   printf("\n \t 1. Insert in Binary Tree  ");

   printf("\n\t 2. Delete from Binary Tree ");
   printf("\n\t 3. Inorder traversal of Binary tree");

   printf("\n\t 4. Postorder traversal of Binary tree");

   printf("\n\t 5. Preorder traversal of Binary tree");
 printf("\n\t 6. Search and replace ");

   printf("\n\t 7. Exit ");
   printf("\n\t Enter choice : ");

   scanf(" %d",&choice);
   if(choice<1 || choice>7)

   printf("\n Invalid choice - try again");
  }

while (choice<1 || choice>7);

  switch(choice)
{

   case 1:
    printf("\n Enter new element: ");

    scanf("%d", &item);


    root= insert(root,item);


    printf("\n root is %d",root->info);


    printf("\n Inorder traversal of binary tree is : ");


    inorder(root);


    break;


   case 2:


   printf("\n Enter the element to be deleted : ");


   scanf(" %d",&item_no);


   root=delet(root,item_no);


   inorder(root);


    break;


   case 3:


   printf("\n Inorder traversal of binary tree is : ");


   inorder(root);


   break;


   case 4:


   printf("\n Postorder traversal of binary tree is : ");


   postorder(root);


   break;


   case 5:


   printf("\n Preorder traversal of binary tree is : ");


   preorder(root);


   break;


   case 6:


   printf("\n Search and replace operation in binary tree ");


   root=search(root);


   break;


   default:


    printf("\n End of program ");


   } /* end of switch */


  }while(choice !=7);


 return(0);


}



struct tree *insert(struct tree *root, int x)

{


 if(!root)


  {


    root=(struct tree*)malloc(sizeof(struct tree));


    root->info = x;


    root->left = NULL;


    root->right = NULL;


    return(root);


  }


  if(root->info > x)


     root->left = insert(root->left,x);


  else


   {


     if(root->info < x)


 root->right = insert(root->right,x);


   }


   return(root);


 }





void inorder(struct tree *root)

 {


    if(root != NULL)


   {


     inorder(root->left);


     printf(" %d",root->info);


     inorder(root->right);


   }


   return;


 }



void postorder(struct tree *root)

 {
    if(root != NULL)

   {


     postorder(root->left);


     postorder(root->right);


     printf(" %d",root->info);


   }


   return;


 }




void preorder(struct tree *root)
 {

    if(root != NULL)


   {


     printf(" %d",root->info);


     preorder(root->left);


     preorder(root->right);


   }


   return;


 }



/* FUNCTION TO DELETE A NODE FROM A BINARY TREE */

 struct tree *delet(struct tree *ptr,int x)


 {


  struct tree *p1,*p2;


  if(!ptr)


  {


    printf("\n Node not found ");


    return(ptr);


  }


  else


  {


     if(ptr->info < x)


     {


      ptr->right = delet(ptr->right,x);


      /*return(ptr);*/


     }


     else if (ptr->info >x)


      {


       ptr->left=delet(ptr->left,x);


       return ptr;


      }


      else                     /* no. 2 else */


       {


 if(ptr->info == x)    /* no. 2 if */

   if(ptr->left == ptr->right) /*i.e., a leaf node*/


    {


     free(ptr);


     return(NULL);


    }


   else if(ptr->left==NULL)  /* a right subtree */


  {


    p1=ptr->right;


   free(ptr);


   return p1;


  }


  else if(ptr->right==NULL)   /* a left subtree */


  {


  p1=ptr->left;


  free(ptr);


  return p1;


  }


  else


  {


   p1=ptr->right;


   p2=ptr->right;


  while(p1->left != NULL)


     p1=p1->left;


  p1->left=ptr->left;


  free(ptr);


  return p2;


  }


      }/*end of no. 2 if */


     }/* end of no. 2 else */


  /* check which path to search for a given no. */


 }


  return(ptr);


}


/* function to search and replace an element in the binary tree */


struct tree *search(struct tree *root)


{


 int no,i,ino;


 struct tree *ptr;


 ptr=root;


 printf("\n Enter the element to be searched :");


 scanf(" %d",&no);


 fflush(stdin);


 while(ptr)


 {


  if(no>ptr->info)


     ptr=ptr->right;


  else if(no<ptr->info)


     ptr=ptr->left;


  else


     break;


 }


 if(ptr)


 {


  printf("\n Element %d which was searched is found and is = %d",no,ptr->info);


  printf("\n Do you want replace it, press 1 for yes : ");


  scanf(" %d",&i);


  if(i==1)


  {


   printf("\n Enter new element :");


   scanf(" %d",&ino);


   ptr->info=ino;

  }


  else


    printf("\n\t It's okay");


 }


 else


   printf("\n Element %d does not exist in the binary tree",no);


 return(root);


}