binary_search_tree.h

数据结构的C语言实现

/*****************************************************************/
/*
* Copyright (c) 2008,北京归创科技有限公司技术部
* All rights reserved.
* 
* 文件名称：binary_search_tree.h
* 用    途：二叉搜索树的接口说明
            此版本二叉树不支持重复关键字
            二叉搜索树和哈希表的区别是能有效支持排序
            二叉搜索树的搜索性能最好的情况等同于二分法搜索
			二分法搜索应用于静态领域，在需要动态维护的情况下，因为插入的沉重代价（数组整体后移），需要二叉搜索树来支持
* 创建日期：2008年7月17日
*/

/*****************************************************************/


#ifndef DS_BINARY_SEARCH_TREE_H
#define DS_BINARY_SEARCH_TREE_H

#include "ds_define.h"

#define NO_FATHER 0
#define LEFT_CHILD 1
#define RIGHT_CHILD 2

typedef struct bst_value
{
	void *key,*data;//关键字和内容指针
} bst_value;

typedef struct bst_node
{
	bst_value *kv;
	struct bst_node *left;//左孩子
	struct bst_node *right;//右孩子
} bst_node;

typedef struct binary_search_tree
{
	bst_node *root;//树根
	unsigned int entrycount;//节点数量
	int (*equalbykey)(const void *key1,const void *key2);//插入和搜索时使用的关键字比较方法，由外部定义
} binary_search_tree;

/*****************************************************************/
/*
* 创建关键字为int类型的二叉树
*/
/*****************************************************************/
binary_search_tree *bst_create_intkey();

/*****************************************************************/
/*
* 创建关键字为字符串的二叉树
*/
/*****************************************************************/
binary_search_tree *bst_create_stringkey();

/*****************************************************************/
/*
* 创建二叉树
* equalbykey：关键字比较函数
*/
/*****************************************************************/
binary_search_tree *bst_create(int (*equalbykey)(const void *key1,const void *key2));


/*****************************************************************/
/*
* 插入元素，若成功返回DS_SUCCESS，否则返回对应的错误代码
*/
/*****************************************************************/
DS_RESULT bst_insert(const void *key,const void *data,binary_search_tree *bst);

/*****************************************************************/
/*
* 删除指定的关键字的元素
* 另外一种实现则是在节点中放置一个标志位，标志是否删除，实际搜索的时候忽略标志删除的节点
* 参数说明：
* freekey：若为TRUE，则同时释放外部传入的key指针，否则不释放key指针
* freedata：若为TRUE，则同时释放外部传入的data指针，否则不释放data指针
  若key或者data指针指向栈自动分配的空间，此时freekey或者freedata为TRUE时此方法将出错
*/
/*****************************************************************/
void bst_remove_bykey(void *key,BOOL freekey,BOOL freedata,binary_search_tree *bst);

/*****************************************************************/
/*
* 根据指定的关键字在二叉树中搜索，返回结果值，若搜索不到，则返回NULL
*/
/*****************************************************************/
void *bst_search_bykey(const void *key,const binary_search_tree *bst);

/*****************************************************************/
/*
* 哈希不能有效支持排序
* 排序返回元素，返回结果值数组，n为数组长度，若二叉树中没有元素或者内存错误，则返回NULL
* 此方法返回的bst_vlaue使用完毕要显式释放
*/
/*****************************************************************/
bst_value **bst_sort(int *len,const binary_search_tree *bst);

/*****************************************************************/
/*
* 释放二叉树
* 参数说明：
* bst：要释放的二叉树
* freekey：若为TRUE，则同时释放外部传入的key指针，否则不释放key指针
  若key指针指向栈自动分配的空间，此时freekey为TRUE时此方法将出错
* freedata：若为TRUE，则同时释放外部传入的data指针，否则不释放data指针
  若data指针指向栈自动分配的空间，此时freedata为TRUE时此方法将出错
*/
/*****************************************************************/
void bst_free(binary_search_tree *bst,BOOL freekey,BOOL freedata);


#endif