Concept of BST in C

tree.c

/**
 *
 *  ADT: Binary search tree
 *  Definition
 *
 *  http://github.com/kdzlvaids/algorithm
 *
 */

#include <stdlib.h>
#include "tree.h"

#define  ADT_QUEUE_VALUE_TYPE   adt_tree_pair_type*
#include "queue.h"

adt_tree*
adt_tree_create(const adt_tree_compare_func compare, const adt_tree_size_type size_of_key, const adt_tree_size
{
    adt_tree* tree  = (adt_tree*)malloc(sizeof(struct adt_tree_adt_tree));
    tree->size_     = 0;
    tree->root_     = NULL;
    tree->compare_  = compare;
    tree->size_of_key_ = size_of_value;
    tree->size_of_value_ = size_of_value;
}

void
adt_tree_destroy(adt_tree* tree)
{
    adt_tree_clear(tree);
    free(tree);
}

void
adt_tree_postorder_traverse_for_destroy(adt_tree_pointer node)
{
    if(node == NULL) return;

    adt_tree_postorder_traverse_for_destroy(node->left_);
    adt_tree_postorder_traverse_for_destroy(node->right_);
    free(element->first);
    free(element->second);
    free(element);
    free(node);
}

void
adt_tree_clear(adt_tree* tree)
{
    adt_tree_postorder_traverse_for_destroy(tree->root_);

    tree->size_     = 0;
    tree->root_     = NULL;
}

void
adt_tree_insert(adt_tree* tree, const adt_tree_pair_type pair)
{
    adt_tree_pair_type* element = (adt_tree_pair_type*)malloc(sizeof(adt_tree_pair_type));

    element->first = (adt_tree_key_type)malloc(size_of_key_);
    memcpy(element->first, &pair.first, size_of_key_);

    element->second = (adt_tree_value_type)malloc(size_of_value_);
    memcpy(element->second, &pair.second, size_of_value_);

    adt_tree_pointer node = (adt_tree_pointer)malloc(sizeof(adt_tree_node_type));
    node->element_  = element;
    node->left_     = NULL;
    node->right_    = NULL;
    node->parent_   = NULL;


    if(adt_tree_empty(tree))
        tree->root_ = node;
    else
    {
        adt_tree_pointer n = tree->root_;
        adt_tree_pointer p = NULL;
        do
        {
            p = n;

            if(tree->compare_(pair->first, n->element_->first) < 0)
                n = n->left_;
            else
                n = n->right_;
        }
        while(n != NULL);

        node->parent_ = p;
        if(tree->compare_(pair->first, p->element_->first) < 0)
            p->left_  = node;
        else
            p->right_ = node;
    }

    ++tree->size_;
}

void
adt_tree_erase(adt_tree* tree, const adt_tree_key_type key)
{
    if(! adt_tree_empty(tree))
    {
        adt_tree_pointer n = tree->root_;
        adt_tree_compare_type comp;
        while(n != NULL)
        {
            comp = tree->compare_(key, n->element_->first);
            if(comp == 0)
            {
                if(n->left_ != NULL && n->right_ != NULL) /* Node n has two children */
                {
                    /* Remove one child */
                    adt_tree_pointer p = adt_tree_node_successor(tree, n); /* Successor has only one child */
                    adt_tree_element_swap(n, p); /* So swap with successor */
                    n = p; /* Now node has one child */
                }

                if(n->left_ != NULL)
                {
                    if(n == tree->root_)
                        tree->root_         = n->left_;
                    else if(n->parent_->left_ == n)
                        n->parent_->left_   = n->left_;
                    else
                        n->parent_->right_  = n->left_;
                }
                else
                {   /*  Case one: node n has a right child  -- n->right_ is right child node
                        Case two: node n not have any child -- n->right_ is NULL */

                    if(n == tree->root_)
                        tree->root_         = n->right_;
                    else if(n->parent_->left_ == n)
                        n->parent_->left_   = n->right_;
                    else
                        n->parent_->right_  = n->right_;
                }
                --tree->size_;

                free(n);
                break;
            }

            if(comp < 0)
                n = n->left_;
            else
                n = n->right_;
        }
    }
}

adt_tree_size_type
adt_tree_inorder_traverse_for_count(adt_tree_pointer node, const adt_tree_key_type key, const adt_tree_compare
{
    if(node == NULL) return 0;

    adt_tree_compare_type comp = compare(node->element_->first, key);
    if(comp > 0) return 0;

    adt_tree_size_type count = 0;

    count += adt_tree_inorder_traverse_for_count(node->left_, key, compare);
    if(comp == 0) count += 1;
    count += adt_tree_inorder_traverse_for_count(node->right_, key, compare);

    return count;
}

adt_tree_pair_type*
adt_tree_find(adt_tree* tree, const adt_tree_key_type key)
{
    if(! adt_tree_empty(tree))
    {
        adt_tree_pointer n = tree->root_;
        adt_tree_compare_type comp;
        while(n != NULL)
        {
            comp = tree->compare_(key, n->element_->first);

            if(comp == 0)
                return n->element_;

            if(comp < 0)
                n = n->left_;
            else
                n = n->right_;
        }
    }

    return NULL;
}

void
adt_tree_traverse_levelorder(adt_tree* tree, void (* do_something)(adt_tree_pair_type*))
{
    if(! adt_tree_empty(tree))
    {
        adt_tree_pointer node = tree->root_;

        adt_queue* queue_pair = adt_queue_create();
        adt_queue_push(queue_pair, node->element_);

        while(adt_queue_size(queue_pair) > 0)
        {
            adt_tree_pair_type* pair = (adt_tree_pair_type*)adt_queue_front(queue_pair);
            adt_queue_pop(queue_pair);

            do_something(pair);

            if(node->left_ != NULL) adt_queue_push(queue_pair, node->left_->element_);
            if(node->right_ != NULL) adt_queue_push(queue_pair, node->right_->element_);
        }
    }
}

void
adt_tree_traverse_inorder_using_node(adt_tree_pointer node, void (* do_something)(adt_tree_pair_type*))
{
    if(node == NULL) return;

    adt_tree_traverse_preorder_using_node(node->left_, do_something);
    do_something(node->element_);
    adt_tree_traverse_preorder_using_node(node->right_, do_something);
}

void
adt_tree_traverse_preorder_using_node(adt_tree_pointer node, void (* do_something)(adt_tree_pair_type*))
{
    if(node == NULL) return;

    do_something(node->element_);
    adt_tree_traverse_preorder_using_node(node->left_, do_something);
    adt_tree_traverse_preorder_using_node(node->right_, do_something);
}

void
adt_tree_traverse_postorder_using_node(adt_tree_pointer node, void (* do_something)(adt_tree_pair_type*))
{
    if(node == NULL) return;

    adt_tree_traverse_preorder_using_node(node->left_, do_something);
    adt_tree_traverse_preorder_using_node(node->right_, do_something);
    do_something(node->element_);
}

void
adt_tree_element_swap(adt_tree_pointer first, adt_tree_pointer second)
{
    adt_tree_pair_type* temp = first->element_;
    first->element_ = second->element_;
    second->element_ = temp;
}

adt_tree_pointer
adt_tree_node_successor(adt_tree* tree, const adt_tree_pointer node)
{
    adt_tree_pointer n = node;

    if(n != NULL)
    {
        if(n->right_ != NULL)
        {
            n = n->right_;
            while(n->left_ != NULL)
                n = n->left_;
        }
        else
        {
            while(n->parent_ != NULL)
            {
                if(n == n->parent_->right_)
                {
                    n = n->parent_;
                    break;
                }

                n = n->parent_;
            }
        }
    }

    return n;
}

adt_tree_pointer
adt_tree_node_predecessor(adt_tree* tree, const adt_tree_pointer node)
{
    adt_tree_pointer n = node;

    if(n != NULL)
    {
        if(n->left_ != NULL)
        {
            n = n->left_;
            while(n->right_ != NULL)
                n = n->right_;
        }
        else
        {
            while(n->parent_ != NULL)
            {
                if(n == n->parent_->left_)
                {
                    n = n->parent_;
                    break;
                }

                n = n->parent_;
            }
        }
    }

    return n;
}

tree.h

/**
 *
 *  ADT: Binary search tree
 *  Declaration
 *
 *  http://github.com/kdzlvaids/algorithm
 *
 */

#ifndef ALGORITHM_ADT_TREE_H_
#define ALGORITHM_ADT_TREE_H_ 1

#ifdef __cplusplus
extern "C"
{
#endif

#ifndef ADT_TREE_KEY_TYPE
#define ADT_TREE_KEY_TYPE       void*
#endif

#ifndef ADT_TREE_VALUE_TYPE
#define ADT_TREE_VALUE_TYPE     void*
#endif

typedef ADT_TREE_KEY_TYPE       adt_tree_key_type;
typedef ADT_TREE_VALUE_TYPE     adt_tree_value_type;

struct adt_tree_pair
{
    const   adt_tree_key_type           first;
            adt_tree_value_type         second;
};

typedef struct  adt_tree_pair   adt_tree_pair_type;

typedef size_t                  adt_tree_size_type;
typedef int                     adt_tree_boolean_type;
#ifndef FALSE
#   define FALSE    0
#endif
#ifndef TRUE
#   define TRUE     1
#endif

struct adt_tree_node
{
            adt_tree_pair_type*         element_;
    struct  adt_tree_node*              left_;
    struct  adt_tree_node*              right_;
    struct  adt_tree_node*              parent_;
};

typedef struct  adt_tree_node           adt_tree_node_type;
typedef         adt_tree_node_type*     adt_tree_pointer;
typedef const   adt_tree_node_type*     adt_tree_const_pointer;

typedef         int                     adt_tree_compare_type;
typedef         adt_tree_compare_type   (* adt_tree_compare_func)(adt_tree_key_type, adt_tree_key_type);

struct adt_tree_adt_tree
{
    adt_tree_size_type          size_;
    adt_tree_pointer            root_;
    const adt_tree_compare_func       compare_;
    const adt_tree_size_type          size_of_key_;
    const adt_tree_size_type          size_of_value_;
};

typedef struct  adt_tree_adt_tree       adt_tree;

#define adt_tree_empty(tree)                            (adt_tree_boolean_type)(tree->root_ == NULL)
#define adt_tree_size(tree)                             tree->size_

#define adt_tree_count(tree, key)                       adt_tree_inorder_traverse_for_count(tree->root_, key, tree->compare_)

#define adt_tree_traverse_inorder(tree, callback)       adt_tree_traverse_inorder_using_node(tree->root_, callback)
#define adt_tree_traverse_preorder(tree, callback)      adt_tree_traverse_preorder_using_node(tree->root_, callback)
#define adt_tree_traverse_postorder(tree, callback)     adt_tree_traverse_postorder_using_node(tree->root_, callback)

adt_tree*
adt_tree_create(const adt_tree_compare_func compare, const adt_tree_size_type size_of_key, const adt_tree_size_type size_of_value);

void
adt_tree_destroy(adt_tree* tree);

void
adt_tree_postorder_traverse_for_destroy(adt_tree_pointer node);

void
adt_tree_clear(adt_tree* tree);

void
adt_tree_insert(adt_tree* tree, adt_tree_pair_type* pair);

void
adt_tree_erase(adt_tree* tree, const adt_tree_key_type key);

adt_tree_size_type
adt_tree_inorder_traverse_for_count(adt_tree_pointer node, const adt_tree_key_type key, const adt_tree_compare_func compare);

adt_tree_pair_type*
adt_tree_find(adt_tree* tree, const adt_tree_key_type key);

void
adt_tree_traverse_levelorder(adt_tree* tree, void (* do_something)(adt_tree_pair_type*));

void
adt_tree_traverse_inorder_using_node(adt_tree_pointer node, void (* do_something)(adt_tree_pair_type*));

void
adt_tree_traverse_preorder_using_node(adt_tree_pointer node, void (* do_something)(adt_tree_pair_type*));

void
adt_tree_traverse_postorder_using_node(adt_tree_pointer node, void (* do_something)(adt_tree_pair_type*));

void
adt_tree_element_swap(adt_tree_pointer first, adt_tree_pointer second);

adt_tree_pointer
adt_tree_node_successor(adt_tree* tree, const adt_tree_pointer node);

adt_tree_pointer
adt_tree_node_predecessor(adt_tree* tree, const adt_tree_pointer node);

#ifdef __cplusplus
}
#endif

#endif /* ! ALGORITHM_ADT_TREE_H_ */