叉搜索树(Binary Search Tree)的一般形式如下图所示，每个节点中的元素大于它的左子树中的所有元素，小于它的右子树中的所有元素。对该图中的二叉树进行中序遍历得到一个从小到大排列的有序序列。

      本文给出了上述二叉树的一个C语言实现，包括二叉树的节点添加，删除，查找等等。源码分为三个文件，
使用VC 6.0编译，其中bstree.h是二叉搜索树的数据结构和函数声明，bstree.c是二叉搜索树的函数实现，main.c是
二叉树的测试文件。这里实现的二叉搜索树的增、删、查三个操作的平均时间复杂度都为log2N,其中N为元素个数。
但是如果建树时的元素本身有序，那么上述操作的时间复杂度将会退化为O(N)。

/*
* File : bstree.h
* Purpose: implementation of a Binary Search Tree
* Author: puresky
* Comiler: VC 6.0
* Language: C
*/

#ifndef _BINARY_SEARCH_TREE_H
#define _BINARY_SEARCH_TREE_H

// Binary Search Tree Node Struct
typedef struct BSTNodeStruct BSTNode;
struct BSTNodeStruct
{
        int _key;
        void *_data;
        struct BSTNodeStruct *_left;
        struct BSTNodeStruct *_right;
};

//Binary Search Tree Struct
typedef struct BSTreeStruct BSTree;
struct BSTreeStruct
{
        BSTNode *_root;
        int _count;
};

BSTree *bstree_new();
void bstree_free(BSTree *bst);
void bstree_insert(BSTree *bst, int key, void *data);
void bstree_remove(BSTree *bst, int key);
BSTNode *bstree_find(BSTree *bst, int key);
int bstree_size(BSTree *bst);
int bstree_height(BSTree *bst);
void bstree_print(BSTree *bst);

#endif

 

/*
* File : bstree.c
* Purpose: implementation of a Binary Search Tree
* Author: puresky
* Comiler: VC 6.0
* Language: C
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "bstree.h"


static BSTNode *bstnode_new(int key, void *data)
{
        BSTNode *bstn = (BSTNode *)malloc(sizeof(BSTNode));
        bstn->_key = key;
        bstn->_data = data;
        bstn->_left = bstn->_right = NULL;
        fprintf(stdout, "create BSTNode:%d\n", key);
        return bstn;
}

static void bstnode_free(BSTNode *bstn)
{
        if(bstn)
        {
                fprintf(stdout, "free BSTNode :%d\n", bstn->_key);
                free(bstn);
        }
}

static void bstnode_free_recursively(BSTNode *bstn)
{
        if(bstn)
        {
                if(bstn->_left)
                        bstnode_free_recursively(bstn->_left);
                if(bstn->_right)
                        bstnode_free_recursively(bstn->_right);
                bstnode_free(bstn);
        }
}
static int bstnode_insert(BSTNode **pbstn, int key, void *data)
{
        BSTNode *bstn = *pbstn;
        if(bstn == NULL)
        {
                *pbstn = bstnode_new(key, data);
                return 1;
        }
        else if(bstn->_key > key)
        {
                return bstnode_insert(&bstn->_left, key, data);
        }
        else if(bstn->_key < key)
        {
                return bstnode_insert(&bstn->_right, key, data);
        }
        else //bstn->_key == key
        {
                return 0;
        }
}

static BSTNode *bstnode_find(BSTNode *bstn, int key)
{
        if(bstn == NULL)
                return NULL;
        else if(bstn->_key == key)
                return bstn;
        else if(bstn->_left && bstn->_key > key)
                return bstnode_find(bstn->_left, key);
        else if(bstn->_right && bstn->_key < key)
                return bstnode_find(bstn->_right, key);
        else
                return NULL;
}

//To delete the max Node in the Tree
static int bstnode_remove_left_max(BSTNode **pbstn, BSTNode *toRemove)
{
        BSTNode *bstn = *pbstn;
        if(bstn->_right != NULL)
        {
                bstnode_remove_left_max(&bstn->_right, toRemove);
        }
        else
        {
                toRemove->_key = bstn->_key;
                toRemove->_data = bstn->_data;
                *pbstn = bstn->_left;
                bstnode_free(bstn);
        }
}

static int bstnode_remove(BSTNode **pbstn, int key)
{
        BSTNode *bstn = *pbstn;
        if(bstn == NULL)
                return 0;

        if(bstn->_key > key)
        {
                return bstnode_remove(&bstn->_left, key);
        }
        else if(bstn->_key < key)
        {
                return bstnode_remove(&bstn->_right, key);
        }
        else //bstn->_key == key
        {
                if(bstn->_left == NULL)
                {
                        *pbstn = bstn->_right;
                        bstnode_free(bstn);
                }
                else if(bstn->_right == NULL)
                {
                        *pbstn = bstn->_left;
                        bstnode_free(bstn);
                }
                else //bstn->right != NULL && bstn->left != NULL
                {
                        //Both the left and the right are not NULL.
                        //We can choose either of them to apply a deletion.
                        //Here we choose the left child!
                        //Actually, we find the max node in the left subtree.
                        //And store the data in of max node in the node to be removed really.
                        //Then delete the max node!
                        bstnode_remove_left_max(&bstn->_left, bstn);
                }
        }
}


static int bstnode_height(BSTNode *bstn)
{
        int ret, left, right;
        if(!bstn)
                ret = 0;
        else
        {
                left = bstnode_height(bstn->_left);
                right = bstnode_height(bstn->_right);
                ret = (left > right ? left : right) + 1;
        }
        return ret;
}

static void bstnode_print(BSTNode *bstn, int depth)
{
        int i;
        for(i = 0; i < depth; ++i) printf("  ");
        if(bstn)
        {
                printf("[%d]\n", bstn->_key);
                bstnode_print(bstn->_left, depth + 1);
                bstnode_print(bstn->_right, depth + 1);
        }
        else
        {
                printf("NULL\n");
        }
}

BSTree *bstree_new()
{
        BSTree *bst = (BSTree *)malloc(sizeof(BSTree));
        bst->_count = 0;
        bst->_root = NULL;
        return bst;
}

void bstree_free(BSTree *bst)
{
        if(bst)
        {
                bstnode_free_recursively(bst->_root);
                free(bst);
        }
}

void bstree_insert(BSTree *bst, int key, void *data)
{
        if(bstnode_insert(&bst->_root, key, data))
                bst->_count++;
}

void bstree_remove(BSTree *bst, int key)
{
        if(bstnode_remove(&bst->_root, key))
                bst->_count--;
}

BSTNode *bstree_find(BSTree *bst, int key)
{
        return bstnode_find(bst->_root, key);
}

int bstree_size(BSTree *bst)
{
        return bst->_count;
}

int bstree_height(BSTree *bst)
{
        return bstnode_height(bst->_root);
}

void bstree_print(BSTree *bst)
{
        printf("size:%d, height:%d\n",
                bst->_count,
                bstree_height(bst));
        bstnode_print(bst->_root, 0);
}

/*
* File : main.c
* Purpose: implementation of a Binary Search Tree
* Author: puresky
* Comiler: VC 6.0
* Language: C
*/
#include <stdio.h>
#include <stdlib.h>
#include "bstree.h"

#define MAX_NUM 10

void test()
{
        int i;
        int a[] ={7, 9, 12, 5, 4, 2, 10, 8, 7, 6, 3, 100, 20, 1};
        BSTree *bst = bstree_new();
        for(i = 0; i < sizeof(a) / sizeof(int); ++i)
                bstree_insert(bst, a[i], NULL);
        bstree_print(bst);
       
        printf("==================================\n");
        printf("%d\n", bstree_find(bst, 10)->_key);
        printf("%d\n", bstree_find(bst, 3)->_key);
       
        printf("==================================\n");
        bstree_remove(bst, 4);
        bstree_remove(bst, 1);
        bstree_remove(bst, 10);
        bstree_remove(bst, 3);
        bstree_remove(bst, 7);
        bstree_print(bst);
       
        bstree_free(bst);
}

int main(int argc, char **argv)
{
        test();
        system("pause");
}