二叉查找树

代码实现了二叉树的创建、查找、插入、删除、遍历。

以下着重说删除，分3种情况：
case 1：要删除的节点t即有左子树又有右子树，如图c的node 5
case 2：要删除的节点即没左子树又没右子树，如图a的node 13
case 3：要删除的节点有单支子树，或左或右，如图b的node 16或node 10，另外也要注册被删除节点是父亲的左还是右子树

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

typedef struct BiTree {
    int data;
    struct BiTree* lchild;
    struct BiTree* rchild;
}BST;

void visit_node(BST* t)
{
    if(t != NULL)
        printf("%d\n", t->data);
}

/* 遍历整个树，中序遍历 */
void traverse_tree(BST* t)
{
    if(t == NULL)
        return;
    traverse_tree(t->lchild);
    visit_node(t);
    traverse_tree(t->rchild);
}
#if 0
/* 插入节点，递归方法 */
BST* insert_node_recursion(BST** t, int v)
{
    if(*t == NULL) {
        *t = (BST*)malloc(sizeof(BST));
        (*t)->data = v;
        (*t)->lchild = (*t)->rchild = NULL;
        return *t;
    }

    if (v < (*t)->data)
        (*t)->lchild = insert_node_recursion(&((*t)->lchild), v);
    else
        (*t)->rchild = insert_node_recursion(&((*t)->rchild), v);

    return *t;
}
#else
/* 插入节点，递归方法 */
BST* insert_node_recursion(BST* t, int v)
{
    if(t == NULL) {
        BST* n;
        n = (BST*)malloc(sizeof(BST));
        n->data = v;
        n->lchild = n->rchild = NULL;
        return n;
    }

    if (v < t->data)
        t->lchild = insert_node_recursion(t->lchild, v);
    else if(v > t->data)
        t->rchild = insert_node_recursion(t->rchild, v);

    return t;
}
#endif

/* 插入节点，普通方法 */
BST* insert_node_normal(BST* t, int v)
{
    BST* pre = NULL;
    BST* new = NULL;
    BST* head = t;
    int l, r;

    while(t && t->data != v) {
        pre = t;
        l = r = 0;
        if(v < t->data) {
            l = 1;
            t = t->lchild;
        } else {
            r = 1;
            t = t->rchild;
        }
    }

    new = (BST*)malloc(sizeof(BST));
    new->data = v;
    new->lchild = new->rchild = NULL;

    if (pre != NULL)
        l ? (pre->lchild = new) : (pre->rchild = new);

    if(head == NULL)
        return new;
    else
        return head;
}

/* 查找节点 */
BST* search_node(BST* t, int v)
{
    int level = 0;

    while (t) {
        level++;
        if(v == t->data) {
            printf("found it, deep level is %d\n", level);
            break;
        } else if(v < t->data)
            t = t->lchild;
        else
            t = t->rchild;
    }

    if(!t) {
        printf("node %d is not exist.\n", v);
        return NULL;
    } else
        return t;
}

/* 删除节点 */
void delete_node(BST* t, int v)
{
    BST* pre = NULL;
    BST* find = NULL;
    BST* parent = NULL;
    BST* most_left = NULL;
    int l, r;

    while (t) {
        if(v == t->data) {    //找到要删除的这个节点了
            find = t;
            if(t->lchild && t->rchild) {    //case 1：要删除的节点t即有左子树又有右子树，删除过程总3步

                //找到t的右子树里的最左节点 @1步
                t = t->rchild;
                while (t->lchild) {
                    parent = t;                //记录最左结点的父亲
                    t = t->lchild;
                }
                most_left = t;

                //最左节点代替被删除节点t的位置 @2步
                find->data = most_left->data;

                //上面有人被删除带走，最左节点升职上去了，所以要重新调整下最左节点的上下关系，并删除其占用的空间 @3步
                if (most_left->rchild)
                    parent->lchild = most_left->rchild;
                else
                    parent->lchild = NULL;
                free(most_left);
                most_left = NULL;

                break;
            }
            else if(!t->lchild && !t->rchild)    //case 2：要删除的节点即没左子树又没右子树
                //l为真表示要删除的节点是父亲的左孩子，所以把左子树指针置空，否则置空右子树指针
                l ? (pre->lchild = NULL) : (pre->rchild = NULL);

            else if(t->lchild)                    //case 3：要删除的节点有左子树
                //要删除的结点为t，t的父亲是pre，t有个左儿子是t->lchild
                //t被带走了，所以把t的孩子过继给t的父亲pre，也就是爷爷来带孙子
                //那么爷爷是左胳膊牵着孙子走还是右胳膊呢，那得看t是pre的左孩子还是右孩子
                //l为真表示要删除的节点t是父亲pre的左孩子，所以把t的孩子过继给父亲pre的左子树，否则就过继给右子树
                l ? (pre->lchild = t->lchild) : (pre->rchild = t->lchild);

            else if(t->rchild)                    //case 4：要删除的节点有右子树
                //同case 3一样，都是过继孙子给爷爷的故事，只不过这个是右孩子，case 3是左孩子
                r ? (pre->rchild = t->rchild) : (pre->lchild = t->rchild);

            free(find);
            find = NULL;
            break;
        } else if(v < t->data) {
            pre = t;    //pre代表当前节点的父亲
            l = 1;        //l变量为真表示当前节点是父亲节点的左子树
            r = 0;
            t = t->lchild;
        } else {
            pre = t;
            r = 1;        //r变量为真表示当前节点是父亲节点的右子树
            l = 0;
            t = t->rchild;
        }
    }
}

/* 创建二叉查找树 */
void create_bitree(BST** t, int *d, int len)
{
    int i;

    for(i = 0; i < len; i++)
//        *t = insert_node_recursion(*t, d[i]);
        *t = insert_node_normal(*t, d[i]);
}

void main(void)
{
    //T是整个树的根
    BST* T = NULL;
    int n = 0;
//    int d[] = {4, 13, 3, 9, 28, 6};
    int d[] = {4, 13, 3, 9};

    while(d[n++] != 0);

    create_bitree(&T, d, n - 1);
//    insert_node_recursion(T, 15);
    insert_node_normal(T, 15);
    traverse_tree(T);
    printf("\n\n");
//    search_node(T, 9);
    delete_node(T, 4);
    traverse_tree(T);
}