Made my first binary search tree

Wow.

After spending the last couple of hours nailing down a delete function all I have to say now is I finally (if i didnt already) understand all the fuss over being careful with pointers and the pains they cause.

I have to say making the tree program was great practice with pointers but now I look at my delete function (which works fine, for all cases) and just think "ugh, now thats ugly".

Also, I was wondering if anyone would like to share a delete function that they wrote in C (for a binary search tree of course). From what others have told me I went about it the right way, its just that I thought there would be a better way. I just had to recur through the tree until a NULL, blah blah blah.... ;)

Might want to check out Prelude's Binary Tree Tutorial here for some code to look at (deletion related stuff is towards the middle of that page).

Now I want to upgrade it so that it can use different data types. I know I will have to cast values and use void pointers, but I am unsure how to go about this. Can someone point me to a detailed explanation of void pointers, that are used as parameters to functions?

The hope is to have generic functions that can create trees of integers and char strings and such.

EDIT: Also, anyone got an idea of how I could put this to use (for testing purposes)? I just keep chaning the main function to try out the other functions, but I would like to put it to some sort of reasonable use.

>Might want to check out Prelude's Binary Tree Tutorial here for some code to look at
Better yet, check out the updated and improved version on my website. :)

>I know I will have to cast values and use void pointers, but I am unsure how to go about this.
The concept is simple. Your tree assumes nothing and only works with nodes. You can pass a function that compares items:

Code:

---

struct node {
  void *data;
  struct node *left, *right;
};

struct tree {
  struct node *root;
  int (*compare) ( const void *a, const void *b );
};

---

If you don't mind me posting some quick and dirty code, here is the concept:

Code:

---

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct node {
  void *data;
  struct node *left, *right;
};

struct tree {
  struct node *root;
  int (*compare) ( const void *a, const void *b );
};

struct node *insert_r ( struct node *root,
  struct node *item, int (*cmp) ( const void *a, const void *b ) )
{
  if ( root == NULL )
    root = item;
  else if ( cmp ( item->data, root->data ) < 0 )
    root->left = insert_r ( root->left, item, cmp );
  else
    root->right = insert_r ( root->right, item, cmp );

  return root;
}

void insert ( struct tree *tree, struct node *item )
{
  tree->root = insert_r ( tree->root, item, tree->compare );
}

void print ( struct node *root, int level )
{
  int i;

  if ( root == NULL ) {
    for ( i = 0; i < level; i++ )
      printf ( "\t" );
    printf ( "~\n" );
  }
  else {
    print ( root->right, level + 1 );

    for ( i = 0; i < level; i++ )
      printf ( "\t" );
    printf ( "%s", (char *)root->data );

    print ( root->left, level + 1 );
  }
}

char *dupstr ( const char *s )
{
  char *ret = malloc ( strlen ( s ) + 1 );

  if ( ret == NULL )
    return NULL;

  return strcpy ( ret, s );
}

int compare ( const void *a, const void *b )
{
  return strcmp ( (const char *)a, (const char *)b );
}

int main ( void )
{
  struct tree t = {0, &compare};
  struct node *item;
  char buffer[BUFSIZ];

  while ( fgets ( buffer, sizeof buffer, stdin ) != NULL ) {
    item = malloc ( sizeof *item );
    item->data = dupstr ( buffer );
    item->left = item->right = NULL;
    insert ( &t, item );
  }

  print ( t.root, 0 );
}

---