Binary Search Tree

This is a discussion on Binary Search Tree within the C Programming forums, part of the General Programming Boards category; I am doing a binary search tree. I need some hints on how to do the insert and find. Anyone? ...

  1. #1
    Registered User
    Join Date
    Oct 2005
    Posts
    2

    Binary Search Tree

    I am doing a binary search tree. I need some hints on how to do the insert and find. Anyone?


    Code:
    #include <stdio.h>
    #define MAX_SIZE 32    /* should be a power of two */
    #define EMPTY -1       /* special value to indicate empty node */
    
    typedef int tree [MAX_SIZE];
    /* Defines 'tree' as the type of an array of MAX_SIZE integers. */
    
    void initialize_tree (tree t)
    {
      int i;
      for( i = 0;  i < MAX_SIZE;  i++ )
        {
          t[i] = -1;
        }
    }
    
    void print_tree(tree t)
    {
      int i;
      for(i = 1;  i < MAX_SIZE;  i++)
        {
          if(t[i] == EMPTY) { printf(". "); }
          else { printf("%d ", t[i]); }
        }
      printf("\n");
    }
    
    void bst_insert(tree t, int v)
    {
      /*** HERE  ***/
    
    }
    
    int bst_find(tree t, int v)  /* return 1 if found, 0 if not */
    {
    
      /*** HERE ***/
      return 0;
    }
    
    int ask_for_number()
    {
      int x;
      printf("Enter an integer, or %d to quit.\n", EMPTY);
      scanf("%d", &x);
      return x;
    }
    
    int main()
    {
      tree t;
      int x;
    
      initialize_tree(t);
      x = ask_for_number();
      while(x != EMPTY)
        {
          bst_insert(t, x);
          print_tree(t);
          x = ask_for_number();
        }
      printf("DONE INSERTING.  Now you may query.\n");
      x = ask_for_number();
      while(x != EMPTY)
        {
          if(bst_find(t, x)) { printf("FOUND.\n"); }
          else { printf("NOT FOUND.  :(\n"); }
          x = ask_for_number();
        }
      return 0;
    }

  2. #2
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  3. #3
    Rabble Rouser Slacker's Avatar
    Join Date
    Dec 2005
    Posts
    116
    >I need some hints on how to do the insert and find.
    The big trick to just about anything in a bst is getting the search down pat. To search you check the current node, if the thing you're looking for is less than the current node, you move left. Otherwise you move right. When you get the a match, you found what you're looking for. If it's not found, you'll get to a null pointer:
    Code:
    int search ( struct node *t, int x )
    {
      if ( t == NULL ) /* Not found */
        return 0;
      else if ( t->thing == x ) /* Found */
        return 1;
      else if ( x < t->thing ) /* Go left */
        return search ( t->left, x );
      else /* Go right */
        return search ( t->right, x );
    }
    Insertion is just a planned unsuccessful search, where you insert a new node when you get to the bottom. The big trick is that you need to update the tree, so going back up you need to make sure that the higher parts of the tree know about the changes to the lower parts:
    Code:
    struct node *insert ( struct node *t, int x )
    {
      if ( t == NULL ) { /* Not found, insert */
        t = malloc ( sizeof *t );
        t->thing = x;
        t->left = t->right = NULL;
        return t;
      }
      else if ( t->thing == x ) /* Found, ignore */
        return t;
      else if ( x < t->thing ) /* Go left */
        return search ( t->left, x );
      else /* Go right */
        return search ( t->right, x );
    }
    The biggest part to most bst routines is the search, so if you understand that you'll be well on your way.

    Cheers!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. BST (Binary search tree)
    By praethorian in forum C++ Programming
    Replies: 3
    Last Post: 11-13-2005, 09:11 AM
  3. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 05:15 PM
  4. binary search and search using binary tree
    By Micko in forum C++ Programming
    Replies: 9
    Last Post: 03-18-2004, 10:18 AM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21