tree.cpp

tree implementation in c. good program.

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

 

typedef struct b_tree

{

 int val;

 struct b_tree *left,*right;

}*BT;

//---------------------------------------------------------------------------

typedef struct que

{

 BT val;

 struct que *next;

}*Q;

//---------------------------------------------------------------------------

Q new_node1()

{

 Q new;

 new=malloc(sizeof(struct que));

 new->next=NULL;

 return(new);

}

//---------------------------------------------------------------------------

void add_q(Q head,BT t)

{

 Q temp,new;

 new=new_node1();

 new->val=t;

 temp=head;

 while(temp->next!=NULL)

   temp=temp->next;

 temp->next=new;

}

//---------------------------------------------------------------------------

BT del_q(Q head)

{

 Q temp;

 temp=head->next;

 if(temp!=NULL)

  head->next=temp->next;

 return(temp->val);

}

//---------------------------------------------------------------------------

int q_empty(Q head)

{

  return(head->next==NULL);

}

//---------------------------------------------------------------------------

BT new_node()

{

 BT new;

 new=malloc(sizeof(struct b_tree));

 new->left=new->right=NULL;

 return(new);

}

//---------------------------------------------------------------------------

BT get_node()

{

 BT new;

 new=new_node();

 printf("\n\n\t ENTER THE VER :: ");

 scanf("%d",&new->val);

 return(new);

}

//---------------------------------------------------------------------------

BT create()

{

 BT head,new,temp;

 int attach;

 char c;

 head=new_node();

 new=get_node();

 head->left=new;

 printf("\n\n\t WANT TO ADD ANYMORE NODE (Y/N) :: ");

 c=getche();

 while(c=='Y'||c=='y')

  {

   temp=head->left;

   new=get_node();

   attach=0;

   while(attach==0)

   {

   if(new->val<temp->val)

      if(temp->left!=NULL)

       temp=temp->left;

      else

       {

        temp->left=new;

        attach=1;

       }

   else

       if(temp->right!=NULL)

        temp=temp->right;

       else

        {

         temp->right=new;

         attach=1;

        }

      }

      printf("\n\n\t ANYMORE NODE (Y/N) :: ");

      c=getche();

  }

 return(head);

}

//---------------------------------------------------------------------------

void display(BT temp,int x,int y)

{

 if(temp!=NULL)

  {

   gotoxy(x,y);

   printf("%d",temp->val);

   display(temp->left,x-8,y+4);

   display(temp->right,x+8,y+4);

  }

}

//---------------------------------------------------------------------------

void display1(BT head)

{

 BT temp;

 Q h;

 int i=0;

 h=new_node1();

 temp=head->left;

 add_q(h,temp);

 add_q(h,head);

 temp=del_q(h);

 printf("\n\n\t LEVEL %d :: ",i);

 i++;

 while(!q_empty(h))

 {

  if(temp!=head)

  {

  printf("\t%d",temp->val);

  if(temp->left!=NULL)

   add_q(h,temp->left);

  if(temp->right!=NULL)

   add_q(h,temp->right);

  }

  else

   {

      printf("\n\n\t LEVEL %d :: ",i);

      add_q(h,head);

      i=i+1;

   }

  temp=del_q(h);

 }

}

//---------------------------------------------------------------------------

int search_val(BT head,int val)

{

 BT temp;

 Q h;

 temp=head->left;

 h=new_node1();

 add_q(h,temp);

 while(!q_empty(h))

 {

  temp=del_q(h);

  if(temp->val==val)

      return(1);

  else

   {

      if(temp->left!=NULL)

       add_q(h,temp->left);

      if(temp->right!=NULL)

       add_q(h,temp->right);

   }

 }

 return(0);

}

//---------------------------------------------------------------------------

void pre_order(BT temp)

{

 if(temp!=NULL)

  {

   printf("%d\t",temp->val);

   pre_order(temp->left);

   pre_order(temp->right);

  }

}

//---------------------------------------------------------------------------

void in_order(BT temp)

{

 if(temp!=NULL)

  {

   in_order(temp->left);

   printf("%d\t",temp->val);

   in_order(temp->right);

  }

}

//---------------------------------------------------------------------------

void post_order(BT temp)

{

 if(temp!=NULL)

  {

   post_order(temp->left);

   post_order(temp->right);

   printf("%d\t",temp->val);

  }

}

//---------------------------------------------------------------------------

void mirror(BT temp)

{

 BT t;

 if(temp!=NULL)

  {

   mirror(temp->left);

   mirror(temp->right);

   t=temp->left;

   temp->left=temp->right;

   temp->right=t;

  }

}

//---------------------------------------------------------------------------

 

void main()

{

 BT head;

 int choice,val;

 textcolor(10);

 while(1)

 {

  clrscr();

  printf("\n\n\t ******  BINARY SEARCH TREE *****");

  printf("\n\n\t 1> CREATE");

  printf("\n\n\t 2> DISPLAY");

  printf("\n\n\t 3> PREORDER");

  printf("\n\n\t 4> INORDER");

  printf("\n\n\t 5> POSTORDER");

  printf("\n\n\t 6> SEARCH VAL");

  printf("\n\n\t 7> MIRROR IMAGE");

  printf("\n\n\t 8> EXIT");

  printf("\n\n\t ENTER YOUR CHOICE :: ");

  scanf("%d",&choice);

 

  switch(choice)

  {

   case 1:head=create();

              clrscr();

              printf("\n\n\t THE BINARY SEARCH TREE IS :: ");

              printf("\n\n\t LEVEL WISE :: ");

              display1(head);

              display(head->left,40,20);

              break;

   case 2:clrscr();

              printf("\n\n\t THE BINARY SEARCH TREE IS :: ");

              printf("\n\n\t LEVEL WISE :: ");

              display1(head);

              display(head->left,40,20);

              break;

   case 3:printf("\n\n\t THE PREORDER TRAVERSAL OF THE TREE IS :: ");

              printf("\n\n\t ");

              pre_order(head->left);

              break;

   case 4:printf("\n\n\t THE INORDER TRAVERSAL OF THE TREE IS :: ");

              printf("\n\n\t ");

              in_order(head->left);

              break;

   case 5:printf("\n\n\t THE POSTORDER TRAVERSAL OF THE TREE IS :: ");

              printf("\n\n\t ");

              post_order(head->left);

              break;

   case 6:printf("\n\n\t ENTER THE VAL TO BE SERACHED :: ");

              scanf("%d",&val);

              val=search_val(head,val);

              if(val==1)

               {

                  printf("\n\n\t THE VAL IS PRESENT IN THE TREE");

                  printf("\n\n\t ");

                  display(head->left,40,20);

               }

              else

               {

                  printf("\n\n\t THE VAL IS NOT PRESENT IN THE TREE");

                  printf("\n\n\t ");

                  display(head->left,40,20);

               }

              break;

   case 7:clrscr();

              printf("\n\n\t THE BINARY SERACH TREE IS :: ");

              printf("\n\n\t LEVEL WISE :: ");

              display1(head);

              printf("\n\n\t THE MIRROR IMAGE OF THE TREE IS :: ");

              mirror(head->left);

              display(head->left,40,20);

              break;

   case 8:printf("\n\n\t PRESS ESC KEY TO EXIT");

              if(getch()==27)

               exit(0);

              break;

 

  }

  getch();

 }

}

//---------------------------------------------------------------------------