Binary tree

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

#define KEY_LEN     100
#define VALUE_LEN   100
#define BUF_LEN     100

typedef struct tnode {
    char key[KEY_LEN];
    char value[VALUE_LEN];
    struct tnode *left;
    struct tnode *right;
    struct tnode *parent;
} tnode;

tnode *btree_insert(char *key, char *val, tnode *t, tnode *p)
{
    if (t == NULL) {
        t = calloc(1, sizeof(tnode));
        strcpy(t->key, key);
        strcpy(t->value, val);
        t->parent = p;
    }
    else {
        int cmp = strcmp(key, t->key);
        if (cmp < 0)
            t->left = btree_insert(key, val, t->left, t);
        else if (cmp > 0)
            t->right = btree_insert(key, val, t->right, t);
        else
            printf("key [%s] is already inserted\n", t->key);
    }
    return t;
}

tnode *btree_search(char *key, tnode *t)
{
    if (t != NULL) {
        int cmp = strcmp(key, t->key);
        if (cmp < 0)
            return btree_search(key, t->left);
        else if (cmp > 0)
            return btree_search(key, t->right);
    }
    return t;
}

void btree_destroy(tnode *t)
{
    if (t == NULL)
        return;
    btree_destroy(t->left);
    btree_destroy(t->right);
    free(t);
}

static tnode *reinsert_btree(tnode *dont, tnode *t, tnode *top, tnode *p)
{
    if (t == NULL)
        return top;
    top = reinsert_btree(dont, t->left, top, p);
    if (t != dont)
        top = btree_insert(t->key, t->value, top, p);
    return reinsert_btree(dont, t->right, top, p);
}

tnode *btree_delete(char *key, tnode *t)
{
    tnode *top = t;
    tnode *d;

    d = btree_search(key, t);
    if (d != NULL) {
        tnode *gp = NULL;
        if (d->parent) {
            if (d->parent->left == d)
                d->parent->left = NULL;
            else
                d->parent->right = NULL;
            gp = d->parent->parent;
        }
        t = reinsert_btree(d, d, d->parent, gp);
        if (d == top)
            top = t;

        btree_destroy(d);
    }
    return top;
}

#define STRING_LEN  9
static void draw_string(char *s, char pad)
{
    int i = 0;
    while (s[i])
        putchar(s[i++]);
    while (i++ < STRING_LEN)
        putchar(pad);
}

static void draw_line_to_left(int *line_to_left, int cnest)
{
    while (cnest--)
        draw_string(*line_to_left++ ? "|" : " ", ' ');
    draw_string("+", '-');
}

static void draw_btree(tnode *t, int cnest)
{
    static int line_to_left[26] = {0};

    if (t != NULL) {
        draw_string(t->key, '-');

        line_to_left[cnest] = 1;
        draw_btree(t->right, cnest + 1);

        draw_line_to_left(line_to_left, cnest);

        line_to_left[cnest] = 0;
        draw_btree(t->left, cnest + 1);

    } else {
        printf("(null)\n");
    }
}

static void show_node(tnode *t)
{
    printf("key:[%s]\tvalue:[%s]\tleft:[%s]\tright:[%s]\tparent:[%s]\n",
                    t->key, t->value,
                    t->left  == NULL ? "null" : t->left->key,
                    t->right == NULL ? "null" : t->right->key,
                    t->parent == NULL ? "null" : t->parent->key);
}

static void show_btree(tnode *t)
{
    if (t == NULL)
        return;
    show_btree(t->left);
    show_node(t);
    show_btree(t->right);
}

typedef enum {
    CMD_NONE, CMD_INSERT, CMD_DELETE, CMD_SEARCH, CMD_SHOW, CMD_QUIT
} cmd;

static cmd get_cmd()
{
    cmd ret = CMD_NONE;
    char buf[BUF_LEN];

    while (ret == CMD_NONE) {
        printf("insert/delete/search/show/quit = ");
        if (scanf(" %s", buf) == EOF)
            ret = CMD_QUIT;
        else if (!strcmp(buf, "insert"))
            ret = CMD_INSERT;
        else if (!strcmp(buf, "delete"))
            ret = CMD_DELETE;
        else if (!strcmp(buf, "search"))
            ret = CMD_SEARCH;
        else if (!strcmp(buf, "show"))
            ret = CMD_SHOW;
        else if (!strcmp(buf, "quit"))
            ret = CMD_QUIT;
    }
    return ret;
}

int main(void)
{
    int quit;
    char key[KEY_LEN], val[VALUE_LEN];
    tnode *top = NULL, *search;

#ifdef DEBUG
    int i;
    for (i = 0; i < 10; i++) {
        do {
            int n = rand() % 10;
            sprintf(key, "%d", n);
            sprintf(val, "%d%d%d", n, n, n);
        } while (btree_search(key, top) != NULL);
        top = btree_insert(key, val, top, NULL);
    }
#endif

    quit = 0;
    while (!quit) {
        switch (get_cmd()) {
        case CMD_INSERT:
            printf("key value: ");
            scanf("%s %s", key, val);
            top = btree_insert(key, val, top, NULL);
            break;
        case CMD_DELETE:
            printf("key: ");
            scanf("%s", key);
            top = btree_delete(key, top);
            break;
        case CMD_SEARCH:
            printf("key: ");
            scanf("%s", key);
            search = btree_search(key, top);
            if (search != NULL)
                show_node(search);
            break;
        case CMD_SHOW:
            draw_btree(top, 0);
            show_btree(top);
            break;
        case CMD_QUIT:
            quit = 1;
            break;
        default:
            break;
        }
    }
    btree_destroy(top);
    return 0;
}