Implementação de Binary Search Tree (BST) em C

Aqui está código que implementa uma simples árvore binária de pesquisa. Não têm auto-balanceamento (nem tão pouco uma função para o fazer).

Ficheiro: bstree.h

/*
 *  GPL
 *
 *  Written by Diogo Sousa aka orium
 *  Copyright (C) 2008 Diogo Sousa
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef BSTREE_H_
#define BSTREE_H_

struct bstree_node
{
    void *data;

    struct bstree_node *left;
    struct bstree_node *right;
};

extern int bstree_add(struct bstree_node **,
             void *, 
             int (*)(const void *, const void *));
extern void bstree_walk(struct bstree_node *,
               void (*)(void *));
extern void bstree_free(struct bstree_node *,
               void (*)(void *));
extern void *bstree_search(struct bstree_node *,
              void *,
              int (*)(const void *, const void *));

#endif

Ficheiro: bstree.c

/*
 *  GPL
 *
 *  Written by Diogo Sousa aka orium
 *  Copyright (C) 2008 Diogo Sousa
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

/* TODO: 
 *       * Deletion
 *       * Rebalancing
 */

#include <stdlib.h>

#include "bstree.h"

static struct bstree_node *alloc_bstree_node(void);
static int bstree_insert(struct bstree_node *,
             struct bstree_node *, 
             int (*)(const void *, const void *));
static void *bstree_search_recursive(struct bstree_node *,
                     void *, 
                     int (*)(const void *, const void *));

static struct bstree_node *alloc_bstree_node(void)
{
    struct bstree_node *r;

    r=malloc(sizeof(*r));

    if (r == NULL)
        abort();

    return r;
}

static int bstree_insert(struct bstree_node *tree_node,
             struct bstree_node *node, 
             int (*cmp)(const void *, const void *))
{
    struct bstree_node **dn;
    int d;

    d=cmp(node->data,tree_node->data);

    if (!d)
        return -1;

    if (d > 0)
        dn=&tree_node->right;
    else
        dn=&tree_node->left;

    if (*dn == NULL)
    {
        *dn=node;
        node->left=NULL;
        node->right=NULL;
    }
    else
        return bstree_insert(*dn,node,cmp);

    return 0;
}

int bstree_add(struct bstree_node **root,
           void *data, 
           int (*cmp)(const void *, const void *))
{
    struct bstree_node *node;

    if (data == NULL) /* This may be used as a special value */
        return -1;

    node=alloc_bstree_node();
    node->data=data;

    if (*root == NULL)
    {
        *root=node;
        node->left=NULL;
        node->right=NULL;
        return 0;
    }

    return bstree_insert(*root,node,cmp);
}

void bstree_walk(struct bstree_node *node,
         void (*action)(void *))
{
    if (node == NULL)
        return;

    action(node->data);

    bstree_walk(node->left,action);
    bstree_walk(node->right,action);
}

void bstree_free(struct bstree_node *node,
         void (*action)(void *))
{
    if (node == NULL)
        return;

    if (action != NULL)
        action(node->data);

    bstree_free(node->left,action);
    bstree_free(node->right,action);

    free(node);
}

static void *bstree_search_recursive(struct bstree_node *tree_node,
                     void *needle, 
                     int (*cmp)(const void *, const void *))
{
    struct bstree_node **dn;
    int d;

    d=cmp(needle,tree_node->data);

    if (!d)
        return tree_node->data;

    if (d > 0)
        dn=&tree_node->right;
    else
        dn=&tree_node->left;

    if (*dn != NULL)
        return bstree_search_recursive(*dn,needle,cmp);

    return NULL;
}

void *bstree_search(struct bstree_node *root,
            void *needle,
            int (*cmp)(const void *, const void *))
{
    if (root == NULL)
        return NULL;

    return bstree_search_recursive(root,needle,cmp);
}

Exemplo de uso

FIXME Comentar o código.

/*
 *  GPL
 *
 *  Written by Diogo Sousa aka orium
 *  Copyright (C) 2008 Diogo Sousa
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <stdio.h>
#include <assert.h>

#include "bstree.h"

struct integer
{
    int n;
    char *english;
};

int my_cmp(const void *p1, const void *p2)
{
    return ((struct integer *)p1)->n-((struct integer *)p2)->n;
}

void my_twalk_action(void *data)
{
    printf("%d %sn",((struct integer *)data)->n,
           ((struct integer *)data)->english);
}

int main(void)
{
    struct bstree_node *bstree_root=NULL;
    struct integer i1={1,"one"};
    struct integer i2={2,"two"};
    struct integer i3={3,"three"};  
    struct integer i4={4,"four"};
    struct integer i5={5,"five"};
    struct integer lost={2,NULL};
    struct integer *needle;

    bstree_add(&bstree_root,&i3,my_cmp);
    bstree_add(&bstree_root,&i1,my_cmp);
    bstree_add(&bstree_root,&i5,my_cmp);
    bstree_add(&bstree_root,&i4,my_cmp);
    bstree_add(&bstree_root,&i2,my_cmp);

    bstree_walk(bstree_root,my_twalk_action);

    needle=bstree_search(bstree_root,&lost,my_cmp);

    assert(needle != NULL);

    printf("%sn",needle->english);

    bstree_free(bstree_root,NULL);

    return 0;
}