Thread: Made my first binary search tree

  1. #1
    Prying open my third eye.
    Join Date
    Jun 2005
    Posts
    45

    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....
    "So you're one of those condescending UNIX computer users?"

    "Here's a nickel, kid. Get yourself a better computer."

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    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).
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  3. #3
    Prying open my third eye.
    Join Date
    Jun 2005
    Posts
    45
    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.
    Last edited by Lateralus; 07-21-2005 at 11:32 AM.
    "So you're one of those condescending UNIX computer users?"

    "Here's a nickel, kid. Get yourself a better computer."

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >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 );
    }
    My best code is written with the delete key.

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. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. Binary Search Tree, Inserting node
    By cheryl_li in forum C Programming
    Replies: 1
    Last Post: 09-13-2003, 03:53 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM