bst.c

#include <stdlib.h>
#include <stdio.h>
#include "bst.h"

struct bstnode {
    int key;
    bst *left, *right;
};

static void bst_swap_keys(bst *a, bst *b);
static void bst_newick_rec(const bst *b);
static void *ecalloc(size_t n, size_t s);

int main(void)
{
    bst* b = bst_new(5);

    bst_newick(b);
    bst_insert(&b, 7);

    bst_newick(b);
    bst_insert(&b, 3);

    bst_insert(&b, 8);
    bst_insert(&b, 2);
    bst_insert(&b, 1);
    bst_newick(b);

    bst_remove(&b, 7);
    bst_newick(b);

    bst_delete(&b);
    printf("%p\n", (void*) b);

    return EXIT_SUCCESS;
}

bst *bst_new(int k) {
    bst *b = ecalloc(1, sizeof *b);
    b->key = k;
    return b;
}

void bst_insert(bst **b, int k) {
    if (NULL == b) {
    return;
    }

    if (NULL == *b) {
    *b = bst_new(k);
    } else if ((*b)->key > k) {
    bst_insert(&(*b)->left, k);
    } else if ((*b)->key < k) {
    bst_insert(&(*b)->right, k);
    }
}

bst *bst_search(bst *b, int k) {
    if (NULL == b) {
    return NULL;
    } else if (b->key == k) {
    return b;
    } else if (b->key > k) {
    return bst_search(b->left, k);
    } else {
    return bst_search(b->right, k);
    }
}

bst *bst_min(bst *b) {
    if (NULL != b && NULL != b->left) {
    return bst_min(b->left);
    } else {
    return b;
    }
}

void bst_remove(bst **b, int k) {
    bst *temp;
    if (NULL == b || NULL == *b) {
    return;
    }
    temp = *b;

    if ((*b)->key > k) {
    bst_remove(&(*b)->left, k);
    } else if ((*b)->key < k) {
    bst_remove(&(*b)->right, k);
    } else {
    if (NULL != (*b)->left && NULL != (*b)->right)
    {
        temp = bst_min((*b)->right);
        bst_swap_keys((*b), temp);
        bst_remove(&(*b)->right, k);
    }
    else if (NULL != (*b)->left)
    {
        *b = (*b)->left;
    }
    else if (NULL != (*b)->right)
    {
        *b = (*b)->right;
    }
    else
    {
        (*b) = NULL;
    }
    free(temp);
    }
}

void bst_delete(bst **b) {
    if (NULL == b) {
    return;
    }
    if (NULL != *b) {
    bst_delete(&(*b)->left);
    bst_delete(&(*b)->right);
    free(*b);
    *b = NULL;
    }
}

void bst_newick(const bst *b)
{
    if (NULL != b)
    {
    bst_newick_rec(b);
    printf(";\n");
    }
    else
    {
    printf("NULL!\n");
    }
}

static void bst_newick_rec(const bst *b)
{
    if (NULL == b) {
    return;
    }

    if (NULL != b->left || NULL != b->right) {
    printf("(");
    if (NULL != b->left && NULL != b->right) {
        bst_newick_rec(b->left);
        printf(",");
        bst_newick_rec(b->right);
    } else if (NULL != b->left) {
        bst_newick_rec(b->left);
    } else {
        bst_newick_rec(b->right);
    }
    printf(")");
    }
    printf("%d", b->key);
}

static void bst_swap_keys(bst *a, bst *b)
{
    int temp;
    if (NULL != a && NULL != b && a != b)
    {
    temp = a->key;
    a->key = b->key;
    b->key = temp;
    }
}

static void *ecalloc(size_t n, size_t s) {
    void *o = calloc(n, s);
    if (NULL == o) {
    fprintf(stderr, "Memory allocation failed!\n");
    exit(EXIT_FAILURE);
    }
    return o;
}