Tuesday 15 October 2013

Binary Search Tree

Binary search Tree
In Binary Search Tree & Left child of each node is smaller than parent node.& right child of each node is bigger than root node.And it is applicable to each node of tree.

TRAVERSAL :-

INORDER : It traverse as Left then Node then Right (LNR).
PREORDER: It traverse as NODE then LEFT then RIGHT (NLR). 
POSTORDER: It traverse as Left then Right then Node (LNR).

                      C PRogram :


 // all operation on Binary Search Tree  
 #include<stdio.h>  
 #include<malloc.h>  
 #include<stdlib.h>  
 struct node  
 {  
      struct node *lc;  
      struct node *rc;  
      char data;  
 };  
 typedef struct node node; //typedef  
 void insert(node **,char);  
 void inorder(node *);  
 void preorder(node *);  
 void postorder(node *);  
 void main()  
 {  
      node *root,*par=NULL,*rnode=NULL;  
      root=NULL;  
      int i,k;  
      int f=0;  
      char c;  
      printf("\n NO of element u wan't to insert :");  
      scanf("%d",&k);  
      getchar();  // use to take enter as input in to buffer to prevent it as input in next char input  
      for(i=0;i<k;i++)  
      {  
           printf("\n insert %dth charactor element :",i+1);  
           scanf("%c",&c);  
           getchar();  
           insert(&root,c);  
      }  
      /*------------------------------------traversal-------------------------------*/  
      printf("\n inorder traversal :\n");  
      inorder(root);  
      printf("\n preorder traversal :\n");  
      preorder(root);  
      printf("\n postorder traversal :\n");  
      postorder(root);  
      /*-----------------------End of traversal-------------------------------*/  
 }// end of main  
 /*------------------------------funtion definations--------------------------*/  
 void insert(node **tr,char c)  
 {  
      if(*tr==NULL) // tree is empty so insert as first node  
      {  
           *tr=(node *)malloc(sizeof(node));  
           (*tr)->data=c;  
           (*tr)->rc=NULL;  
           (*tr)->lc=NULL;  
      }  
      else  
      {  
           if(c <(*tr)->data) // COMPARE to decide char to insert as left or right  
           {  
                insert(&(*tr)->lc,c);  
           }  
           else  
             insert(&(*tr)->rc,c);  
      }  
 }  
 void inorder(node *tr) //inorder traversal  
 {  
      if(tr!=NULL)  
      {  
           inorder(tr->lc);  
           printf(" %c ",tr->data);  
           inorder(tr->rc);  
      }  
 }  
 void preorder(node *tr) //preorder traversal  
 {  
      if(tr!=NULL)  
      {  
           printf(" %c ",tr->data);  
           preorder(tr->lc);  
           preorder(tr->rc);  
      }  
 }  
 void postorder(node *tr) //postorder traversal  
 {  
      if(tr !=NULL)  
      {  
     postorder(tr->lc);  
           postorder(tr->rc);  
           printf(" %c ",tr->data);            
      }  
 }  

OUTPUT :

Output binary search tree

1 comment:

THANKS FOR UR GREAT COMMENT

Blogger Widgets