Advertisement
kkricardokaka95

Binary Search tree!

Sep 17th, 2014
223
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.42 KB | None | 0 0
  1. #include<stdio.h>
  2. #include<malloc.h>
  3.  
  4. typedef struct
  5. {
  6.     int data;
  7.     struct node* left;
  8.     struct node* right;
  9. }node;
  10.  
  11. typedef struct
  12. {
  13.     node* root;
  14. }head;
  15.  
  16. void insert(head *t, int ele)
  17. {
  18.     node *p,*q;
  19.     q=t->root;
  20.     p=(node*)malloc(sizeof(node));
  21.     p->left=p->right=NULL;
  22.     p->data=ele;
  23.     if(t->root==NULL)
  24.         t->root=p; 
  25.     else
  26.     {
  27.         while(1)
  28.         {  
  29.             if(q->data<=(p->data)&&q->right==NULL||q->data>(p->data)&&q->left==NULL)
  30.                 break;
  31.             if(p->data>q->data)
  32.                 q=q->right;
  33.             else
  34.                 q=q->left; 
  35.        
  36.         }
  37.         if(q->data<=(p->data))
  38.                 q->right=p;
  39.         else
  40.                 q->left=p;     
  41.        
  42.     }
  43. }  
  44.  
  45. node* search(head *t,int ele)
  46. {
  47.     node *q;
  48.     q=t->root;
  49.     while(q!=NULL)
  50.     {
  51.         if(q->data>ele)
  52.             q=q->left;
  53.         else if(q->data<ele)
  54.             q=q->right;
  55.         else if(q->data==ele)
  56.             return q;  
  57.     }
  58.     return NULL;
  59. }
  60.  
  61. void inorder(node* p)
  62. {
  63.     if(p==NULL)
  64.     {
  65.         printf("\nBinary Search Tree empty.\n");
  66.         return;
  67.     }
  68.     else
  69.     {
  70.         inorder(p->left);
  71.         printf("%d",p->data);
  72.         inorder(p->right); 
  73.     }
  74. }
  75.  
  76. void preorder(node* p)
  77. {
  78.     if(p==NULL)
  79.     {
  80.         printf("\nBinary Search Tree empty.\n");
  81.         return;
  82.     }
  83.     else
  84.     {
  85.        
  86.         printf("%d",p->data);
  87.         inorder(p->right); 
  88.         inorder(p->left);
  89.     }
  90. }
  91.        
  92. void postorder(node* p)
  93. {
  94.     if(p==NULL)
  95.     {
  96.         printf("\nBinary Search Tree empty.\n");
  97.         return;
  98.     }
  99.     else
  100.     {
  101.         inorder(p->left);      
  102.         inorder(p->right); 
  103.         printf("%d",p->data);
  104.     }
  105. }
  106.  
  107.  
  108.  
  109. void main()
  110. {
  111.     int ch,ele;
  112.     head x;
  113.     node* y;
  114.     x.root=NULL;
  115.     while(1)
  116.    {
  117.     printf("\n1.Enter an element in the tree.\n2.Search an element\n3.Display\n4.Exit\n");
  118.     scanf("%d",&ch);
  119.     if(ch==4)
  120.         break;
  121.     switch(ch)
  122.     {
  123.         case 1:
  124.         printf("\nEnter the element to be inserted\n");
  125.         scanf("%d",&ele);
  126.         insert(&x,ele);
  127.         break;
  128.             case 2:
  129.             printf("\nEnter the element to be searched\n");
  130.             scanf("%d",&ele);
  131.             if(search(&x,ele))
  132.                 printf("\nElement is found.\n");
  133.             else
  134.                 printf("\nElement is not found\n");    
  135.         break;
  136.         case 3:
  137.         printf("\n1.Inorder\n2.Preorder\n3.Postorder\nEnter your choice\n");
  138.         scanf("%d",&ch);
  139.         printf("\nEnter the element from which you want to display\n");
  140.         scanf("%d",&ele);
  141.         y=find(&x,ele);
  142.         switch(ch)
  143.         {
  144.             case 1: inorder();
  145.             break;
  146.             case 2: preorder();
  147.             break;
  148.             case 3: postorder();
  149.             break;
  150.         }
  151.         break;
  152.         default:
  153.         printf("\nInvalid choice\n");
  154.     }      
  155.     }
  156. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement