bstree.c

红黑树和二叉查找树数据结构的实现以及二者的性能比较的C语言实现代码

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


static int bsCount;

struct bsTreeNode
{
    bsTreeNode parent;
    bsTreeNode left;
    bsTreeNode right;
    bsKEY bskey;
};

struct bsTree
{
	bsTreeNode root;
};


bsTree BS_NewTree()
{
	bsTree T;
    if (NULL == (T = (bsTree)malloc(sizeof(*T))))
    {
        printf("Memory alloc error\n");
        return NULL;
    }
    T->root = NULL;
	return T;
}


bsTreeNode BS_Search(bsTreeNode x, bsKEY bskey)
{
	if (x==NULL || bskey == x->bskey)
		return x;
	if (bskey < x->bskey)
		return BS_Search(x->left, bskey);
	else
		return BS_Search(x->right, bskey);
}


bsTreeNode BS_Search_Iterative(bsTreeNode x, bsKEY bskey)
{
	while (x !=NULL && bskey != x->bskey)
	{
		if (bskey <x->bskey)
			x = x->left;
		else
			x = x->right;
	}
	return x;
}


bsTreeNode BS_SearchInTree(bsTree T, bsKEY key)
{
	bsTreeNode n;
    n = BS_Search(T->root, key);
	if (NULL != n)
		return n;
	else
		return NULL;
}

bsTreeNode BS_Search_IterativeInTree(bsTree T, bsKEY key)
{
	bsTreeNode n;
    n = BS_Search_Iterative(T->root, key);
	if (NULL != n)
		return n;
	else
		return NULL;
}


bsTreeNode BS_Minimum(bsTreeNode x)
{
	while (x->left != NULL)
		x = x->left;
	return x;
}

bsTreeNode BS_Maximum(bsTreeNode x)
{
	while (x->right != NULL)
		x = x->right;
	return x;
}


bsTreeNode BS_Successor(bsTreeNode x)
{
	bsTreeNode y;
	if (x->right != NULL)
		return BS_Minimum(x->right);
	y = x->parent;
	while (y !=NULL && x == y->right)
	{
		x = y;
		y = y->parent;
	}
	return y;
}


bsTreeNode BS_Predecessor(bsTreeNode x)
{
	bsTreeNode y;
	if (x->left != NULL)
		return BS_Maximum(x->left);
	y = x->parent;
	while (y !=NULL && x == y->left)
	{
		x = y;
		y = y->parent;
	}
	return y;
}


bsTree BS_Insert(bsTree T, bsKEY bskey)
{
	bsTreeNode x, y;
    bsTreeNode z;
    x = T->root, y = NULL;
    /*while (NULL != x)
    {
		if (bskey == x->bskey)
		{
			printf("The bskey %d is already in the tree!\n",bskey);
			return T;
		}
        y = x;
		x = (bskey<x->bskey) ? 
			x->left : x->right;
	}*/
	while (x != NULL)
	{
		y = x;
		if (bskey <x->bskey)
			x = x->left;
		else
			x = x->right;
	}
	 // 把z放到合适的位置
	if (NULL == (z = (bsTreeNode)malloc(sizeof(*z))))
    {
        printf("Memory alloc error\n");
        return T;
    }
	z->parent = y;
    z->left = NULL;
    z->right = NULL;
    z->bskey = bskey;
    if (NULL == y)
    {
        T->root = z;
    }
    else
    {
        if (z->bskey < y->bskey)
            y->left = z;
        else
            y->right = z;
    }
	return T;
}

bsTree BS_Delete(bsTree T, bsKEY bskey)
{
	bsTreeNode x, y, z;
	z = BS_Search_Iterative(T->root, bskey);
    if (NULL == z)
	{
		printf("NO this bskey in the tree!\n");
		return T;
	}
	// 当z有一个空子树的时候,y == z
	if (NULL == z->left || NULL == z->right)
		y = z;
	// 否则,y是大于z最小的结点
    else
		y = BS_Successor(z);
	// x is y's only child
	if (NULL != y->left)
        x = y->left;
    else
        x = y->right;  
	// 设定x的位置取代y
	if (NULL != x)
		x->parent = y->parent;
    if (NULL == y->parent)
        T->root = x;
    else if (y == y->parent->left)
        y->parent->left = x;
    else
        y->parent->right = x; // 把y的bskey拷贝到z中
	if (y != z)
    {
        z->bskey = y->bskey;
    } 
	free(y);
	return T;
}



void BS_Print_Node(bsTreeNode node)
{
	printf("%d",node->bskey);
}


void BS_Free_Node(bsTreeNode node)
{
	free (node);
}


void BS_Pre_Visit(bsTreeNode node, bsProcess process)
{
	if (node != NULL)
	{
		process(node);
		BS_Pre_Visit(node->left, process);
		BS_Pre_Visit(node->right, process);
	}
}


void BS_In_Visit(bsTreeNode node,bsProcess process)
{
	if (node != NULL)
	{
		BS_In_Visit(node->left, process);
		process(node);
		BS_In_Visit(node->right, process);
	}
}


void BS_Post_Visit(bsTreeNode node, bsProcess process)
{
	if (node != NULL)
	{
		BS_Post_Visit(node->left, process);
		BS_Post_Visit(node->right, process);
		process(node);
	}
}


void BS_Pre_Disply(bsTreeNode node, bsProcess process)
{
	int i;
	if (node == NULL)
	{
		for (i=0;i<bsCount; i++)
			printf("  ");
		printf("NULL");
	}
	else
	{
		for (i=0;i<bsCount; i++)
			printf("  ");
		printf("(");
		process(node);
		printf(" :\n");
		bsCount = bsCount+2;
		BS_Pre_Disply(node->left, process);
		printf(",\n");
		BS_Pre_Disply(node->right, process);
		printf("\n");
		bsCount = bsCount-2;
		for (i=0;i<bsCount; i++)
			printf("  ");
		printf(")");
		
	}
}


void BS_Displiy_Tree(bsTree T, bsVisit visit)
{
	bsTreeNode node;
	node = T->root;
	if (visit == BS_Pre_Disply)
		bsCount = 0;
	visit(node, BS_Print_Node);
	printf("\n");
}


void BS_Delete_Tree(bsTree T, bsVisit visit)
{
	bsTreeNode node;
	node = T->root;
	visit(node, BS_Free_Node);
	printf("\n");
}


bsTree BS_NewTree_Rand(int a[], int n)
{
	int i;
	bsTree T;
	T = BS_NewTree();
	for(i = 0; i < n; i++)
		BS_Insert(T, a[i]);
	return T;
}