BST（二叉搜索树）

BST（Binary Search Tree）目的是为了提高查找的性能，其查找在平均和最坏的情况下都是logn级别，接近二分查找。

其特点是：每个节点的值大于其任意左侧子节点的值，小于其任意右节点的值。

介绍三个最基本的操作：

预备操作：

typedef struct node{
	int value;
	char key;
	int Index;
	struct node *left;
	struct node *right;
}BSTNode,*PBSTNode;

1、查找

//找到指定的键值
PBSTNode  Get(PBSTNode root,char Key)
{
	if(!root)
		return NULL;
	if(Key == root->key)
		return root;
	else if(Key < root->key)
		return Get(root->left,Key);
	else
		return Get(root->right,Key);
}

2、插入节点操作。

//插入操作
//------1.BSTree为空-------------------------
//------2.BSTree已经有该键，那么只需要更新
//------3.正常操作---------------------------
void BSTInsert(PBSTNode *root,char Key,int Value)
{
	//树开始是空值
	if(!(*root))
	{
		(*root) = (PBSTNode)malloc(sizeof(BSTNode));
		(*root)->Index = 0;
		(*root)->key = Key;
		(*root)->value = Value;
		(*root)->left = (*root)->right = NULL;
		return;
	}
	PBSTNode Temp = (PBSTNode)malloc(sizeof(BSTNode));
	PBSTNode des = Get((*root),Key);
	//已经存在更新键值
	if(des != NULL)
	{
		des->value = Value;
		return;
	}
	//正常的情况下：
	PBSTNode Go = (*root);
	while(Go)
	{
		if(Go->key > Key)
		{
			if(!Go->left)
			{
				Temp->key = Key;
				Temp->value = Value;
				Temp->left = Temp->right = NULL;
				Go->left = Temp;
                //序号没有实现更新。
				return;
			}
			else
				Go = Go->left;
		}//end of > situation
		else
		{
			if(!Go->right)
			{
				Temp->key = Key;
				Temp->value = Value;
				Temp->left = Temp->right = NULL;
				Go->right = Temp;
				return;
			}
			else
				Go = Go->right;
		}
	}
}

我们可以利用插入节点这个函数来进行BST树的创建：

//利用插入函数来创建BSTree
PBSTNode CreateBSTree(char *data,int n)
{
	PBSTNode Root = NULL;
	if(n == 0)
		Root =  NULL;
	else
	{
		for(int i = 0;i < n;i++)
			BSTInsert(&Root,data[i],i);
	}
	return Root;
}

3、删除

//删除操作:
//-------1、未查找到----------------------------------------------------------------------
//-------2、删除的节点只有一个子节点，直接将其删除，并让其父节点指向其唯一的那个子节点即可
//-------3、删除的节点是叶子节点，直接删除就行
//-------4、删除的结点有两个子节点，则有两种方案可供选择：
//-------------------------------------------------------1)选取其右孩子的最小结点来顶替其位置
//-------------------------------------------------------2)选取其左孩子的最大节点来顶替其位置
//返回值-1表示删除非法。1代表成功。
int Delete(PBSTNode * Root,char key)
{
	//删除头结点
	if((*Root)->key == key)
	{
		if(!(*Root)->left && (*Root)->right)
		{
			(*Root) = (*Root)->right;
			free((*Root));
			return 1;
		}
		else if((*Root)->left && !(*Root)->right)
		{
			(*Root) = (*Root)->left;
			free((*Root));
			return 1;
		}
		PBSTNode Min = (PBSTNode)malloc(sizeof(BSTNode));
		Min = (*Root)->right;
		PBSTNode ParentMin = (PBSTNode)malloc(sizeof(BSTNode));
		ParentMin = (*Root);
		while(Min->left)
		{
			ParentMin = Min;
			Min = Min->left;
		}
		ParentMin->left = Min->right;
		Min->left = (*Root)->left;
		Min->right = (*Root)->right;
		(*Root) = Min;
		return 1;
	}
	//因为需要找到删除节点的父节点，所以不能调用Get函数
	PBSTNode Parent = (*Root);
	PBSTNode Go = (*Root);
	while(Go)
	{
		if(Go->key == key)
			break;
		else if(Go->key > key)
		{
			Parent = Go;
			Go = Go->left;
		}
		else
		{
			Parent = Go;
			Go = Go->right;
		}
	}
	//Situation 1
	if(!Go)
		return -1;
	//Situation 2
	if(!Go->left && Go->right)
	{
		if(Parent->left == Go)
			Parent->left = Go->right;
		else
			Parent->right = Go->right;
		free(Go);
		return 1;
	}
	else if(Go->left && !Go->right)
	{
		if(Parent->left == Go)
			Parent->left = Go->left;
		else
			Parent->right = Go->left;
		free(Go);
		return 1;
	}
    //Situation 3
	else if(!Go->left && !Go->right)
	{
		if(Parent->left == Go)
			Parent->left = NULL;
		else
			Parent->right = NULL;
		free(Go);
		return 1;
	}
	//Situation 4
	//Choose Solution 1: Min right son
	else
	{
		PBSTNode Min = (PBSTNode)malloc(sizeof(BSTNode));
		Min = Go->right;
		PBSTNode ParentMin = (PBSTNode)malloc(sizeof(BSTNode));
		ParentMin = Go;
		while(Min->left)
		{
			ParentMin = Min;
			Min = Min->left;
		}
		if(Parent->left == Go)
		{
			Parent->left = Min;
			ParentMin->left = Min->right;
			Min->left = Go->left;
			Min->right = Go->right;
		}
		else
		{
			Parent->right = Min;
			ParentMin->left = Min->right;
			Min->left = Go->left;
			Min->right = Go->right;
		}
	}//end of else
	return 1;
}

删除由于情况比较多所以复杂一点。

4、返回范围内的所有数据

//范围查找，找出某个范围内的全部数据,返回一个动态链表
void  GetDatasFromField(PBSTNode Root,char LowKey,char MaxKey,PBSTNode *Result,int *count)
{
	if(!Root)
		return;
	if(Root->key > LowKey && Root->key < MaxKey)
	{
		Result[(*count)] = (PBSTNode)malloc(sizeof(BSTNode));
		Result[(*count)]->key = Root->key;
		Result[(*count)]->value = Root->value;  
		(*count)++;
		//这情况表示左右都有可能有符合范围的数据
		GetDatasFromField(Root->left,LowKey,MaxKey,Result,count);
		GetDatasFromField(Root->right,LowKey,MaxKey,Result,count);
	}
	else if(Root->key < LowKey)
	{
		if(Root->key == LowKey)
		{
			Result[(*count)] = (PBSTNode)malloc(sizeof(BSTNode));
			Result[(*count)]->key = Root->key;
			Result[(*count)]->value = Root->value;
			(*count)++;
		}
		//表明数据在右边
		GetDatasFromField(Root->right,LowKey,MaxKey,Result,count);
	}
	else
	{
		if(Root->key == MaxKey)
		{
			Result[(*count)] = (PBSTNode)malloc(sizeof(BSTNode));
			Result[(*count)]->key = Root->key;
			Result[(*count)]->value = Root->value;
			(*count)++;
		}
		//表明数据在左边
		GetDatasFromField(Root->left,LowKey,MaxKey,Result,count);
	}
}

转载自原文链接, 如需删除请联系管理员。

原文链接：BST（二叉搜索树），转载请注明来源！