Binary Tree made simple

01 Nov 2010

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


struct bt {
    void *data;
    char *key;
    struct bt *right, *left;
};

/* prototypes */
int add_btnode (struct bt **, char *, void *);
void init_bt (struct bt **);
struct bt *search_btnode (struct bt *, char *);
void print_inorder (struct bt *);

int
main (void)
{
    struct bt *root, *p;
    init_bt (&root);
    add_btnode (&root, "Daniel", "C");
    add_btnode (&root, "Bia", "asm");
    add_btnode (&root, "Nelson", "Php");
    p = search_btnode (root, "Bia");
    printf ("Bia is an %s hacker\n", (char *)p->data);
    puts ("\n\nIN ORDER");
    print_inorder (root);
     
    return 0;
}

void
init_bt (struct bt **r)
{
    *r = NULL;
}

int
add_btnode (struct bt **root, char *k, void *dat)
{
    if (!*root) {
        *root = malloc (sizeof (struct bt));
        if (!*root) exit (EXIT_FAILURE);
        (*root)->key = k;
        (*root)->data = dat;
        (*root)->right = (*root)->left = NULL;
        return 0;
    }    
    if (strcmp (k, (*root)->key) > 0)
        add_btnode (&(*root)->right, k, dat);
    else if (strcmp (k, (*root)->key) < 0)
        add_btnode (&(*root)->left, k, dat);
    return -1;
} 

struct bt *
search_btnode (struct bt *root, char *k)
{
    int rval;
    if (!root) return NULL;
    rval = strcmp (k, root->key);
    while (root && rval) {
        if (rval > 0) root = root->right;
        else root = root->left;
        rval = strcmp (k, root->key);
    }
    return root;
}

void
print_inorder (struct bt *root)
{
    if (!root) return;    
        
    print_inorder (root->left);
    printf ("%s => %s\n", root->key, (char *)root->data);
    print_inorder (root->right);
}

Tested at: http://ideone.com/vL1N0