二叉搜索树的C实现

    看再多的算法书数据结构书，都不如自己实现一遍代码来的印象深刻。很多时候我们总是眼高手低的，要看书，更要写代码。 对于IT民工而言，一个讲算法头头世道但无法实现算法的民工，远不如 一个just do it民工。

    吐槽完毕，最近实现了二叉搜索树的算法，和大家分享。不对之处，请各位指正。本文实现的是最基本的二叉搜索树，非平衡二叉搜索树。 

    测试代码在linux下编译通过，同时验证了几轮，暂是没有发现bug。读者可以直接使用这份代码。如何使用这份代码，可以参考测试文件 bst_test.c。

    测试用例，写的不够周全，只是初步体现了测试驱动开发的思想，并没有对每个接口进行详备的测试。

    代码中注释不多，原因有二

    1 二叉搜索树 算法比较简单

    2 我深信：好的代码，是自注释的。

    二叉搜索树中，稍复杂的接口是删除，算法导论中的删除 伪码层次并不清晰，倒是讲述比较清晰。本实现将删除接口按照下面三种情况，分别实现，相对比较好理解。

    1 删除节点 无孩子

    2 删除节点 只有一个孩子

    3 删除节点有两个孩子

版本情况
 V1.0   --实现基本二叉树的插入 删除 查找功能
 V1.1 ----新增select功能，查找第k大的节点。从0开始，即最小节点是bst_select(root,0);

#ifndef _BSTREE_H
#define _BSTREE_H

#define OPERATION_SELECT

typedef int   key_type ;
typedef struct __bst_node
{
    struct __bst_node* parent;
    struct __bst_node* left;
    struct __bst_node* right;
    key_type key;
    int data;

#ifdef OPERATION_SELECT
    int counter;
#endif

}bst_node;

typedef struct __bs_tree
{
    bst_node *bst_root;
}bs_tree;
bst_node* bst_search_aux(bst_node* root,key_type key,bst_node** pparent);
bst_node* bst_search(bst_node* root,key_type key);
bst_node* bst_min(bst_node* root);
bst_node* bst_max(bst_node *root);
bst_node* bst_successor(bst_node* node);
bst_node* bst_predecessor(bst_node* node);
bst_node* bst_allocnode(key_type key,int data);
int  bst_freenode(bst_node* node);
bst_node* bst_insert(bst_node *root,bst_node* node);
bst_node* bst_delete(bst_node* root,bst_node *node);

#endif

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

/* if find the node whose key equal to key,return the node;
  * else return null;
  * if not find and pparent is not null, return the futurn father
  * if your want insert a node whose key is equal to key
  */
bst_node* bst_search_aux(bst_node* root,key_type key,bst_node** pparent)
{
    bst_node *parent = root;
    bst_node* cur = root;

    while(cur&&cur->key != key)
    {
        parent = cur;
        if(cur->key >key)
            cur = cur->left;
        else
            cur = cur->right;
    }

    if(cur == NULL)
    {
        if(pparent != NULL)
            *pparent = parent;
    }
    return  cur;
}

/*just find ,if found,return the node ,else return null*/
bst_node* bst_search(bst_node* root,key_type key)
{
    return bst_search_aux(root,key,NULL);
}

/*find the node whose key is the smallest in the tree*/
bst_node* bst_min(bst_node* root)
{
    bst_node *cur = root;
    if(cur == NULL)
        return NULL;  /*empty tree, return null*/

    while(cur->left != NULL)
        cur = cur->left;

    return cur;
}

bst_node* bst_max(bst_node *root)
{
    bst_node *cur = root;

    if(cur == NULL)
        return NULL;

    while(cur->right)
        cur = cur->right;

    return cur;

}

bst_node* bst_successor(bst_node* node)
{
    bst_node *par;
    bst_node *node_tmp;
    if(node == NULL)
        return NULL;

    if(node->right != NULL)
        return bst_min(node->right);

    par = node->parent;
    node_tmp = node;

    while(par && node_tmp == par->right)
    {
        node_tmp = par ;
        par = par->parent;
    }

    return par;


}

bst_node* bst_predecessor(bst_node* node)
{
    bst_node *par;
    bst_node *node_tmp;

          if(node == NULL)
        return NULL;

    if(node->left != NULL)
    {
        return bst_max(node->left);
    }

    par = node->parent;
    node_tmp = node;

    while (par && node_tmp == par->left)
    {
        node_tmp = par;
        par = par->parent;
    }

    return par;

}


bst_node* bst_allocnode(key_type key,int data)
{
    bst_node *node = NULL;
    node = (bst_node*)malloc(sizeof(bst_node));
    if(node == NULL)
    {
        printf("alloc node failed \n");
        return NULL;
    }


    node->key = key;
    node->data = data    ;
    node->parent = NULL;
    node->left = NULL;
    node->right = NULL;
#ifdef OPERATION_SELECT
    node->counter =  1;
#endif
    return node;
}

int  bst_freenode(bst_node* node)
{
    if(node)
    free(node);

    node = NULL;
    return 0;
}

#ifdef OPERATION_SELECT
bst_node* bst_up_counter(bst_node* root,bst_node* node)
{
    bst_node *cur = root;
    if(root == NULL||node == NULL)
    {
        printf("invalid input,root or node is null\n");
        return NULL;
    }

    while(cur->key != node->key)
    {
        cur->counter++;
        if(cur->key > node->key)
            cur = cur->left;
        else
            cur = cur->right;
    }

    return root;
}

bst_node* bst_down_counter(bst_node *root,bst_node* node)
{
    bst_node *cur = root;
    if(root == NULL|| node == NULL)
    {
        printf("invalid input ,root or node is null\n");
        return NULL;
    }

    while(cur->key != node->key)
    {
        cur->counter--;
        if(cur->key > node->key)
            cur = cur->left;
        else
            cur = cur->right;
    }
    return root;

}

#endif

/* return 0 means succeed,else failed*/
bst_node* bst_insert(bst_node *root,bst_node* node)
{
    bst_node* par;
    bst_node* same_node = NULL;

    if(node == NULL)
    {
        printf("[bst_insert] invalid input ,please check the input\n");
        return root;
    }

    same_node = bst_search_aux( root, node->key, &par);
    if(same_node != NULL)
    {
        printf("same node has been existed ,insert failed \n");
        return root;
    }

    if(par == NULL)
    {
        root = node;
        return root;
    }

    if(node->key >(par)->key)
    {
        (par)->right = node;
    }
    else
    {
        (par)->left = node;
    }

    node->parent = par;
#ifdef OPERATION_SELECT
    root = bst_up_counter(root,node);
#endif

    return root;

}

bst_node* bst_delete(bst_node* root,bst_node *node)
{
    bst_node *par = node->parent;
    bst_node* child;
    bst_node* successor;


    if(root == NULL || node == NULL)
    {
        printf("invalid input ,root or node is null\n");
        return root;
    }

    if(node->left == NULL && node->right == NULL)  /*no child*/
    {

#ifdef OPERATION_SELECT
        bst_down_counter(root,node);
#endif

        if(par)
        {
            if(node == par->left)
                par->left = NULL;
            else
                   par->right = NULL;
        }

        else
         root = NULL;/*no father means root node*/

        bst_freenode(node);

        return root;
    }

    if(node->left == NULL || node->right == NULL) /*only one child*/
    {

#ifdef OPERATION_SELECT
        bst_down_counter(root,node);
#endif
        if(node->left)
            child = node->left;
        else
            child = node->right;

        child->parent = par;

        if(par)
        {
            if(node == par->left)
                par->left = child;
            else

                par->right = child;
        }
        else
        {
            root = child;
        }

        bst_freenode(node);
        return root;
    }

    /*both chld,so successor must be existed*/

    successor = bst_successor(node);
    node->key = successor->key;
    node->data = successor->data;
    return bst_delete(root,successor);

}

#ifdef OPERATION_SELECT
bst_node* bst_select(bst_node* root,int k)
{
    if(root == NULL)
        return NULL;/*not find the kth node*/
    int t=0;
    if(root->left ==NULL)
        t = 0;
    else
        t = root->left->counter;

    if(t>k)
        return bst_select(root->left,k);
    else if(t<k)
        return bst_select(root->right,k-t-1);
    return root;
}

#endif

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

#define random(x) (rand()%(x))

#define N  10
int test_bst()
{
    bs_tree bst;

    bst_node *node[N];
    bst_node *node_4;
    bst_node *node_max;



    int i;
    int array[N];
//    srand((int)time(NULL)) ;
    bst.bst_root = NULL;
    for(i = 0;i<N;i++)
    {
        array[i] = random(100);
    }

    for(i = 0;i<N;i++)
    {
        printf("a[%d] = %d\n",i,array[i]);
    }

    for(i = 0;i<N;i++)
    {
        node[i] = bst_allocnode(array[i],array[i]);
        if(node[i] != NULL)
            bst.bst_root = bst_insert(bst.bst_root,node[i]);
        else
        {
            printf("alloc failed ,should exit\n");
            return -1;
        }
    }

    node_4 = bst_select(bst.bst_root,4);
    if(node_4 == NULL)
    {
        printf("the fourth node is not existed\n");
        return -2;
    }
    printf("the fourth node's key is %d\n",node_4->key);
    bst.bst_root = bst_delete(bst.bst_root,node_4);
    for(i = 0;i<N;i++)
    {
        node_max = bst_max(bst.bst_root);
        if(node_max)
            printf("%d\t",node_max->key);
        else
        {
          printf("find the max failed \n");
            return -2;
        }
        bst.bst_root = bst_delete(bst.bst_root,node_max);
    }

    printf("\n");
    return 0;
}
int main()
{
    test_bst();
    return 0;
}