二叉排序树的定义

二叉排序树，又称二叉查找树，我们这样定义：树非空，对于任意结点存在左子树或右子树，则左子树上所有结点的关键字均小于该结点的关键字，右子树上所有结点的关键字均大于该节点的关键字，这样的二叉树叫二叉排序树。即：

左子树结点值<根结点值<右子树结点值

还有一个默认规定，在二叉排序树中，不能有两个结点关键字相同。

二叉排序树的查找

定义一个二叉树的结构：

typedef struct BSTNode {
	int data;
	struct BSTNode* lchild;
	struct BSTNode* rchild;
}BSTNode,* BSTree;

查找算法的基本思路是，从根节点开始，目标值更小的往左找，目标值更达的往右找，知道目标值和结点值相同，返回该结点。通过递归的方式实现：

BSTNode* Search(BSTree T, int k) {
	if (T == NULL)
		return NULL;
	if (k == T->data)
		return T;
	else if (k < T->data)
		return Search(T->lchild, k);
	else 
		return Search(T->rchild, k);
}

二叉排序树的插入

插入算法的设计思路与查找类似，采用递归的方式，将待插入结点的关键字值与树中各个结点的关键字值进行比较，若小于则向左走，若大于则向右走，知道找到一个空结点，将新结点插入。从算法的实现方式上，我们可以知道，插入结点一定都是叶子结点。下面是算法实现：

Status BST_Insert(BSTree* T, int k) {
	if ((*T) == NULL) {
		(*T) = (BSTree)malloc(sizeof(BSTNode));
		if (!(*T))exit(OVERFLOW);
		(*T)->data = k;
		(*T)->lchild = (*T)->rchild = NULL;
		return OK;//插入成功
	}
	else if (k == (*T)->data)return ERROR;//插入失败
	else if (k < (*T)->data)return BST_Insert(&(*T)->lchild, k);
	else return BST_Insert(&(*T)->rchild, k);
}

二叉排序树的删除

删除算法的实现较为复杂，主要需要考虑结点的类型，来分门别类进行讨论。首先分析，一个结点会有三种情况：

1.该结点是叶子结点，那么可以直接删除；

2.结点只含有左子树或右子树，在删除该节点后，用其子树代替其在原先的位置；

3.结点既含有左子树，有含有右子树，这里有两种处理方法。在待删除结点的位置，可以用待删除结点的后继结点来替代，然后删除后继结点；或者是用待删除的结点的前驱结点来替代，然后删除前驱结点。关于前驱后继结点的位置问题，我们通过中序遍历二叉树的性质，可以知道，在这种情况下，待删除结点的后继是该结点的右子树的最左下结点，前驱是该结点的左子树的最右下结点。

具体代码如下：

Status Delete(BSTree* p)
{
	//从二叉排序树中删除节点p,并重接它的左或右子树
	BSTree q, s;
	if (!(*p)->lchild && !(*p)->rchild)	//p为叶子节点
		*p = NULL;
	else if (!(*p)->lchild)	//左子树为空，重接右子树
	{
		q = *p;
		*p = (*p)->rchild;
		free(q);
	}
	else if (!(*p)->rchild)	//右子树为空，重接左子树
	{
		q = *p;
		*p = (*p)->lchild;
		free(q);
	}
	else						//左右子树均不为空
	{
		q = *p;
		s = (*p)->lchild;
		while (s->rchild)		//转左，然后向右走到尽头
		{
			q = s;
			s = s->rchild;
		}
		(*p)->data = s->data;
		if (q != *p)				//判断是否执行上述while循环
			q->rchild = s->lchild;	//执行上述while循环，重接右子树
		else
			q->lchild = s->lchild;	//未执行上述while循环，重接左子树
		free(s);
	}
	return OK;
}

然后我们遍历用递归的方式实现最终的删除算法：

Status Delete_BST(BSTree* T, int key)
{
	/* 若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素节点 */
	/* 并返回TRUE；否则返回FALSE */
	if (!(*T))
		return FALSE;	//不存在关键字等于key的数据元素
	else
	{
		if (key == (*T)->data)
			Delete(T);
		else if (key < (*T)->data)
			return Delete_BST(&(*T)->lchild, key);
		else
			return Delete_BST(&(*T)->rchild, key);
	}
	return OK;
}

附加：完整代码：

#include<stdio.h>
#include<stdlib.h>
#define TRUE		1
#define OK			1
#define FALSE		0
#define ERROR		0
#define OVERFLOW	-1
typedef struct BSTNode {
	int data;
	struct BSTNode* lchild;
	struct BSTNode* rchild;
}BSTNode,* BSTree;
typedef int Status;

void visit(BSTree T) {
	printf("%d ", T->data);
}
void InOrder(BSTree T) {
	if (T != NULL) {
		InOrder(T->lchild);
		visit(T);
		InOrder(T->rchild);
	}
}
void Create_BSTree(BSTree* T,int arr[],int n) {
	(*T) = NULL;
	int i = 0;
	while (i < n) {
		BST_Insert(T, arr[i]);
		i++;
	}
}
BSTNode* Search(BSTree T, int k) {
	if (T == NULL)
		return NULL;
	if (k == T->data)
		return T;
	else if (k < T->data)
		return Search(T->lchild, k);
	else 
		return Search(T->rchild, k);
}
Status BST_Insert(BSTree* T, int k) {
	if ((*T) == NULL) {
		(*T) = (BSTree)malloc(sizeof(BSTNode));
		if (!(*T))exit(OVERFLOW);
		(*T)->data = k;
		(*T)->lchild = (*T)->rchild = NULL;
		return OK;//插入成功
	}
	else if (k == (*T)->data)return ERROR;//插入失败
	else if (k < (*T)->data)return BST_Insert(&(*T)->lchild, k);
	else return BST_Insert(&(*T)->rchild, k);
}
Status Delete_BST(BSTree* T, int key)
{
	/* 若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素节点 */
	/* 并返回TRUE；否则返回FALSE */
	if (!(*T))
		return FALSE;	//不存在关键字等于key的数据元素
	else
	{
		if (key == (*T)->data)
			Delete(T);
		else if (key < (*T)->data)
			return Delete_BST(&(*T)->lchild, key);
		else
			return Delete_BST(&(*T)->rchild, key);
	}
	return OK;
}
Status Delete(BSTree* p)
{
	//从二叉排序树中删除节点p,并重接它的左或右子树
	BSTree q, s;
	if (!(*p)->lchild && !(*p)->rchild)	//p为叶子节点
		*p = NULL;
	else if (!(*p)->lchild)	//左子树为空，重接右子树
	{
		q = *p;
		*p = (*p)->rchild;
		free(q);
	}
	else if (!(*p)->rchild)	//右子树为空，重接左子树
	{
		q = *p;
		*p = (*p)->lchild;
		free(q);
	}
	else						//左右子树均不为空
	{
		q = *p;
		s = (*p)->lchild;
		while (s->rchild)		//转左，然后向右走到尽头
		{
			q = s;
			s = s->rchild;
		}
		(*p)->data = s->data;
		if (q != *p)				//判断是否执行上述while循环
			q->rchild = s->lchild;	//执行上述while循环，重接右子树
		else
			q->lchild = s->lchild;	//未执行上述while循环，重接左子树
		free(s);
	}
	return OK;
}
void main() {
	BSTree T;
	int array[8] = { 50,66,60,26,21,30,70,68 };
	Create_BSTree(&T, array, 8);
	printf("\n删除结点之前的二叉排序树:");
	InOrder(T);
	printf("\n");
	Delete_BST(&T, 70);
	printf("\n删除70之后的二叉排序树:");
	InOrder(T);
	printf("\n");
}

查找效率的分析

由于二叉排序树的性质，我们中序遍历二叉排序树后，得到的是一个递增序列。二叉排序树的目的不仅仅是为了排序，二叉排序树的主要作用是提高了元素的查找、插入、删除的速度，这也与其链式的存储结构有关。

我们重点关注二叉排序树的查找效率。查找操作的原理是通过比对结点的数值大小，来判定是向左走还是向右走，最后在相等情况下停下来，查找成功。那么，其比较的次数是待查找元素所在的深度，最好的情况是1次，即要找的元素就是根结点，最坏不会超过树的深度。所以，查找性能取决于这颗树的形状。通过平均查找长度(ASL)计算，我们知道，一个二叉排序树应该尽量“平衡”，其深度与完全二叉树相同，这样的树拥有最佳的查找性能。现在的问题是，二叉排序树的形状不是固定的，不一定每一个二叉排序树都具有最佳的查找性能，如何将一个二叉排序树“平衡”，并且仍然保持二叉排序树的性质，是一个很有意义的问题，这就牵扯到平衡二叉树的知识了。