Thread: 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;
}

>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!