Advertisement
Guest User

Binary Search Tree in C

a guest
Feb 22nd, 2012
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.92 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. typedef struct tree_t
  6. {
  7.     int num;
  8.     struct tree_t *left;
  9.     struct tree_t *right;
  10. } tree;
  11.  
  12. tree* search_get_node(int num, tree **head)
  13. {
  14.     tree *curr = *head;
  15.     if(num < curr->num)
  16.     {
  17.         if(curr->left == NULL)
  18.         {
  19.             return curr;
  20.         }
  21.         curr = curr->left;
  22.         return search_get_node(num, &curr);
  23.     }
  24.     if(num > curr->num)
  25.     {
  26.         if(curr->right == NULL)
  27.         {
  28.             return curr;
  29.         }
  30.         curr = curr->right;
  31.         return search_get_node(num, &curr);
  32.     }
  33.  
  34.     if(num == curr->num)
  35.     {
  36.         return curr;
  37.     }
  38. }
  39.  
  40. void add_node(tree *n, tree **head)
  41. {
  42.     tree *curr = search_get_node(n->num, head);
  43.  
  44.     if(n->num < curr->num)
  45.     {
  46.         if(curr->left == NULL)
  47.         {
  48.             curr->left = n;
  49.             return;
  50.         }
  51.     }
  52.     if(n->num > curr->num)
  53.     {
  54.         if(curr->right == NULL)
  55.         {
  56.             curr->right = n;
  57.             return;
  58.         }
  59.     }
  60.     /* If equal, then free & ignore since its already in the tree */
  61.     free(n);
  62. }
  63.  
  64. void add(int num, tree **head)
  65. {
  66.     tree *n = (tree*) malloc(sizeof(tree));
  67.     n->num = num;
  68.     n->left = NULL;
  69.     n->right = NULL;
  70.     add_node(n, head);
  71. }
  72.  
  73. int search(int num, tree **head)
  74. {
  75.     tree* t = search_get_node(num, head);
  76.     return num == t->num;
  77. }
  78.  
  79. void free_tree(tree* head)
  80. {
  81.     if(head == NULL)
  82.     {
  83.         return;
  84.     }
  85.  
  86.     free_tree(head->left);
  87.     free_tree(head->right);
  88.  
  89.     free(head);
  90. }
  91.  
  92. int main(int argc, char** argv)
  93. {
  94.     srand(time(NULL));
  95.     tree *head = (tree*) malloc(sizeof(tree));
  96.     head->num = rand() + 1;
  97.     head->left = NULL;
  98.     head->right = NULL;
  99.     int i;
  100.     for(i = 1; i < 9999999; i++)
  101.     {
  102.         unsigned int n = (rand()) + 1;
  103.         add(n, &head);
  104.     }
  105.  
  106.     free_tree(head);
  107.     return 0;
  108. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement