binary_search_tree.c

数据结构的C语言实现

/*****************************************************************/
/*
* Copyright (c) 2008,北京归创科技有限公司技术部
* All rights reserved.
* 
* 文件名称：binary_search_tree.c
* 用    途：二叉搜索树的实现
* 创建日期：2008年7月17日
*/

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

#include "binary_search_tree.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>

static int default_equalby_intkey(const void *key1,const void *key2)
{
	int k1 = (int)key1;
	int k2 = (int)key2;
	if(k1 == k2) return 0;
	else if(k1 < k2) return -1;
	else return 1;
}
static int default_equalby_stringkey(const void *key1,const void *key2)
{
	return strcmp((char *)key1,(char *)key2);
}
static DS_RESULT bst_insert_node(bst_node *father,bst_node *newnode,binary_search_tree *bst)
{
	int compare_result;
	if(bst->root == NULL)
	{
		bst->root = newnode; 
		bst->entrycount++; 
		return DS_SUCCESS;
	}
	compare_result = bst->equalbykey(newnode->kv->key,father->kv->key);
	if(compare_result == 0) return DS_DUPLICATE_KEY;
	else if(compare_result < 0) 
	{
		if(father->left == NULL)
		{
			father->left = newnode; 
		    bst->entrycount++; 
		    return DS_SUCCESS; 
		}
		else return bst_insert_node(father->left,newnode,bst);
	}
	else 
	{
		if(father->right == NULL)
		{
			father->right = newnode; 
		    bst->entrycount++; 
		    return DS_SUCCESS; 
		}
		else return bst_insert_node(father->right,newnode,bst);
	}
}
static void bst_cut_node(bst_node *father,bst_node *child,int child_pos,binary_search_tree *bst)
{
	bst_node *bn;
	if(father == NULL || child_pos == LEFT_CHILD)
	{
		if(child->left != NULL)
		{
		    if(father == NULL) bst->root = child->left;
			else father->left = child->left;
			bn = child->left;
			while(bn->right != NULL) bn = bn->right;
			bn->right = child->right;
		}
		else 
		{
			if(father == NULL) bst->root = child->right;
			else father->left = child->right;
		}
	}
	else
	{
		if(child->right != NULL)
		{
			father->right = child->right;
			bn = child->right;
		    while(bn->left != NULL) bn = bn->left;
		    bn->left = child->left;
		}
		else father->right = child->left;
	}
}
static void bst_remove_node(void *key,BOOL freekey,BOOL freedata,bst_node *father,bst_node *child,int child_pos,binary_search_tree *bst)
{
    int compare_result;
	if(child == NULL) return;
	compare_result = bst->equalbykey(key,child->kv->key);
	if(compare_result == 0)
	{
		bst_cut_node(father,child,child_pos,bst);
		if(freekey) free(child->kv->key);
		if(freedata) free(child->kv->data);
		free(child->kv);
		free(child);
		bst->entrycount--;
	}
	else if(compare_result < 0) bst_remove_node(key,freekey,freedata,child,child->left,LEFT_CHILD,bst);
	else bst_remove_node(key,freekey,freedata,child,child->right,RIGHT_CHILD,bst);
}
static void *bst_search_node(void *key,bst_node *node,binary_search_tree *bst)
{
	int compare_result;
	if(node == NULL) return NULL;
	compare_result = bst->equalbykey(key,node->kv->key);
	if(compare_result == 0) return node->kv->data;
	else if(compare_result < 0) return bst_search_node(key,node->left,bst);
	else return bst_search_node(key,node->right,bst);
}
static void bst_sort_node(bst_value **bv,int *index,bst_node *node,binary_search_tree *bst)
{
	//中序遍历
	if(node->left != NULL) bst_sort_node(bv,*index,node->left,bst);
	bv[(*index)++] = node->kv;
	if(node->right != NULL) bst_sort_node(bv,*index,node->right,bst);
}
static void bst_free_node(binary_search_tree *bst,bst_node *node,BOOL freekey,BOOL freedata)
{
	if(node->left != NULL) bst_free_node(bst,node->left,freekey,freedata);
    if(freekey) free(node->kv->key);
	if(freedata) free(node->kv->data);
	free(node->kv);
	free(node);
	if(node->right != NULL) bst_free_node(bst,node->right,freekey,freedata);
}
//平衡二叉树，优化搜索性能，待完成（应该完成一个红黑树，可能要求更改插入算法）
static void balance(binary_search_tree *bst)
{
}

binary_search_tree *bst_create_intkey()
{
	return bst_create(default_equalby_intkey);
}
binary_search_tree *bst_create_stringkey()
{
	return bst_create(default_equalby_stringkey);
}
binary_search_tree *bst_create(int (*equalbykey)(const void *key1,const void *key2))
{
	binary_search_tree *bst = MALLOC(binary_search_tree,1);
	if(bst == NULL) return NULL;
	bst->entrycount = 0;
	bst->equalbykey = equalbykey;
	bst->root = NULL;
	return bst; 
}
DS_RESULT bst_insert(const void *key,const void *data,binary_search_tree *bst)
{
	DS_RESULT r;
	bst_node *bn;
	assert(bst);
    bn = MALLOC(bst_node,1);
	if(bn == NULL) return DS_MEMORY_ERROR;
	bn->kv = MALLOC(bst_value,1);
	if(bn->kv == NULL) return DS_MEMORY_ERROR;
	bn->kv->key = key;
	bn->kv->data = data;
	bn->left = bn->right = NULL;
	r = bst_insert_node(bst->root,bn,bst);
	if(r == DS_DUPLICATE_KEY) { free(bn->kv);free(bn); }
	return r;
}
void bst_remove_bykey(void *key,BOOL freekey,BOOL freedata,binary_search_tree *bst)
{
	assert(bst);
	bst_remove_node(key,freekey,freedata,NULL,bst->root,NO_FATHER,bst);
}
void *bst_search_bykey(const void *key,const binary_search_tree *bst)
{
	assert(bst);
	return bst_search_node(key,bst->root,bst);
}
bst_value **bst_sort(int *len,const binary_search_tree *bst)
{
	bst_value **bv;
	int index;
	assert(bst);
	if(bst->entrycount == 0) return NULL;
	bv = MALLOC(bst_value *,bst->entrycount);
	if(bv == NULL) return NULL;
	*len = bst->entrycount;
	index = 0;
	bst_sort_node(bv,&index,bst->root,bst);
	return bv;
}
void bst_free(binary_search_tree *bst,BOOL freekey,BOOL freedata)
{
	assert(bst);
	bst_free_node(bst,bst->root,freekey,freedata);
}