Saturday, May 18, 2013

Binary Tree Implementation in C with Tree Traversals

We can implement the binary tree using C so that we can add a node, delete a node, and can perform different tree traversals:
 1. Preorder tree traversal
 2. Inorder tree traversal
 3. Post order tree traversal




/// ..............................................BINARY TREE OPERATIONS AND TREE TRAVERSALS

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

///.................................................................DYNAMIC STRUCTURE FOR BINARY TREE

struct tree
{
     int info;
     struct tree *left_subtree;
     struct tree *right_subtree;
};

///...................................................................GLOBAL FUNCTIONS DECLARATIONS

 struct tree* make_tree();
 struct tree* delete_node(struct tree*,int);
 void insert_node(struct tree *);
 void preorder(struct tree *);
 void inorder(struct tree *);
 void postorder(struct tree *);

///....................................................................MAIN FUNCTION

int main()
{
  struct tree *p_tree,*t;
  int choice,del_item;

  printf("\n\t_____________________________****OPERATIONS ON BINARY TREE AND TREE TRAVERSALS****_____________________________\n\n");
  printf("\n1. INSERTION");
  printf("\n2. dELETION");
  printf("\n3. PRE-ORdER TRAVERSAL");
  printf("\n4. IN-ORdER TRAVERSAL");
  printf("\n5. POST-ORdER TRAVERSAL");
  printf("\n6. EXIT FROM MENU\n");

  p_tree = NULL;
 do
 {

  printf("\n\t\t\t\t\t\tEnter Choice: ");
  scanf("%d",&choice);
  switch(choice)
  {
  case 1: ///.........................................................INSERTION
     if(p_tree == NULL)
          p_tree = make_tree();

    else
          insert_node(p_tree);
     break;

  case 2: ///..................................................... ..DELETION
     if(p_tree == NULL)
           printf("Binary Tree Empty.......");
     else
     {
         printf("Enter info to delete:");
         scanf("%d",&del_item);
      if(p_tree->left_subtree == NULL && p_tree->right_subtree == NULL && p_tree->info == del_item)
     {
        t = p_tree;
        p_tree = NULL;
        free(t);
      }
      else
        p_tree = delete_node(p_tree,del_item);
     }
      break;

  case 3:/// ......................................................PRE-ORdER TRAVERSAL

        printf("\n\n\tPRE-ORdER TRAVERSAL :\n\t\t\t\t");
     if(p_tree == NULL)
        printf("\nBinary Tree Empty....\n");
     else
        preorder(p_tree);
     break;
  case 4:///..................................................... IN-ORdER TRAVERSAL

        printf("\n\n\tIN-ORdER TRAVERSAL :\n\t\t\t\t");
     if(p_tree == NULL)
        printf("\nBinary Tree Empty....\n");
     else
        inorder(p_tree);
     break;
  case 5:///...................................................... POST-ORdER TRAVERSAL

        printf("\n\n\tPOST-ORdER TRAVERSAL :\n\t\t\t\t");
     if(p_tree == NULL)
        printf("\nBinary Tree Empty....\n");
     else
        postorder(p_tree);
     break;
  case 6: ///...................................................... TO EXIT

       exit(0);
  default:///........................................................dEFAULT CASE

       printf("\n\tPlease,Enter the choice lying among 1 to 4 .\n");
  }

 }while(1);

 getch();
 return 0;
}

struct tree* make_tree() ///..................................ALLOCATES A NOdE & SETS IT AS A ROOT OF THE TREE
{
    struct tree * p_tree;
    p_tree =(struct tree*)malloc(sizeof(struct tree));
    printf("\n\t\tEnter info: ");
    scanf("%d",&p_tree->info);
    p_tree->left_subtree = NULL;
    p_tree->right_subtree = NULL;
    return p_tree;
}

void insert_node(struct tree *p_tree) ///.............................ALLOWS INSERTION OF A NOdE
{
    struct tree *t,*n;
    t = p_tree;
    n =(struct tree *)malloc(sizeof(struct tree));
    printf("\n\t\tEnter info: ");
    scanf("%d",&n->info);
    n->left_subtree = NULL;
    n->right_subtree = NULL;
 while(t->left_subtree != NULL || t->right_subtree != NULL)
 {
     if(t->left_subtree != NULL)
       if(n->info < t->info)
         t = t->left_subtree;
    if(t->right_subtree != NULL)
       if(n->info>= t->info)
         t = t->right_subtree;
    if((t->left_subtree == NULL) && (n->info < t->info) && (n->info <t->right_subtree->info))
         break;
    if((t->right_subtree == NULL) && (n->info >= t->info) && (n->info >t->left_subtree->info))
         break;
 }
    if((n->info < t->info) && (t->left_subtree == NULL))
         t->left_subtree=n;
    if((n->info > t->info) && (t->right_subtree == NULL))
         t->right_subtree = n;
}

void inorder(struct tree * p_tree)  ///..................................................ALLOWS IN-ORDER TRAVERSAL
{
    //printf("\n\t\t");
    if(p_tree != NULL)
  {
     inorder(p_tree->left_subtree);
     printf("%d    ",p_tree->info);
     inorder(p_tree->right_subtree);
 }
}
void preorder(struct tree *p_tree)  ///..................................................ALLOWS PRE-ORDER TRAVERSAL
{
      //printf("\n\t\t");
    if(p_tree != NULL)
    {
        printf("%d   ",p_tree->info);
        preorder(p_tree->left_subtree);
        preorder(p_tree->right_subtree);
    }
}
void postorder(struct tree *p_tree)  ///.................................................ALLOWS POST - ORDER TRAVERSAL
{
    //printf("\n\t\t");
    if(p_tree != NULL)
    {
        postorder(p_tree->left_subtree);
        postorder(p_tree->right_subtree);
        printf("%d    ",p_tree->info);
    }
}

struct tree * delete_node(struct tree *p_tree,int d)  ///................................ALLOWS DELETION OF A NODE
{
     int f = 0,f1 = 0;
     struct tree *p,*t,*t1,*x;
     t = p_tree;

     //to search found or not
   while(t != NULL)
  {
     if(t->info == d)
    {
      f = 1;
      x = t;
       break;
    }
   if(t->info > d)
   {
     p = t;
     t = t->left_subtree;
   }
   else if(t->info <= d)
  {
     p = t;
     t = t->right_subtree;
   }
   }
   if(f == 0)
   {
    printf("\nThe entered  element not found.......\n");
    return p_tree;
  }

   ///........................................................................if the node to be deleted has no sub-tree
if(x->left_subtree == NULL && x->right_subtree == NULL)
   {
     if(p->right_subtree == x)
         p->right_subtree = NULL;
     else
         p->left_subtree = NULL;
     free(x);
     return p_tree;
   }

    ///......................................................................if the node to be deleted  has left & right sub-trees

if(x->left_subtree != NULL && x->right_subtree != NULL)
   {
      p = x;
      t1 = x->right_subtree;
   while(t1->left_subtree != NULL)
   {
      p = t1; f1 = 1;
      t1 = t1->left_subtree;
   }
    if(t1->left_subtree == NULL && t1->right_subtree == NULL)
    {
       x->info = t1->info;
       if(f1 == 1)
          p->left_subtree = t1->left_subtree;
       if(f1 == 0)
          x->right_subtree = t1->right_subtree;
       free(t1);
       return p_tree;
     }
   if(t1->right_subtree != NULL)
   {
       x->info = t1->info;
      if(f1 == 1)
          p->left_subtree = t1->right_subtree;
      if(f1 == 0)
          p->right_subtree = t1->right_subtree;
      free(t1);
      return p_tree;
    }
   }

     ///..........................................................................if the node to be deleted has oniy right sub-tree

if(x->left_subtree == NULL && x->right_subtree != NULL && x->info!= p_tree->info)
   {
   if(p->left_subtree == x)
       p->left_subtree = x->right_subtree;
   else
       p->right_subtree = x->right_subtree;
    free(x);
    return p_tree;
   }

        ///........................................................................if the node to be deleted has oniy left sub-tree

if(x->left_subtree != NULL && x->right_subtree == NULL && x->info != p_tree->info)
   {
        if(p->left_subtree == x)
              p->left_subtree = x->left_subtree;
        else
              p->right_subtree = x->left_subtree;
        free(x);
        return p_tree;
    }
        if(x->left_subtree != NULL && x->right_subtree == NULL && x->info == p_tree->info)
       {
              p_tree = x->left_subtree;
              free(p);
              return p_tree;
         }
        if(x->left_subtree == NULL && x->right_subtree != NULL && x->info == p_tree->info)
       {
           p_tree = x->right_subtree;
           free(p);
           return p_tree;
        }
}

2 comments :

  1. For sports gambling and also other betting games, quite a few staking buffs utilize a Private Toto Site, and there are several things that Private company Toto site should evaluate prior to selecting any website, including, add-ons, operating period, and even more. By visiting this particular web site, you can get understanding about the Private Toto Site.

    ReplyDelete
  2. The slot machines are the most popular games in casinos throughout the world and online alike. They are easy to understand, incredibly fun to play, and for players visiting a land based casino, 안전놀이터

    ReplyDelete

Related Posts Plugin for WordPress, Blogger...