二叉排序树(Binary Sort Tree)，又称二叉查找树，它或者是一棵空树，或者是一棵具有一下性质的树：
- 若它的左子树不空，则左?树上所有结点的值均?于它的根结点的值
- 若它的右子树不空，则右子树上所有结点的值均?于它的根结点的值
- 它的左右子树也分别是二叉排序树
二叉排序树采用了递归的定义方法。左子树结点一定比双亲结点小，右子树结点一定比双亲结点大。因为需要做删除插入操作，所有我们选择链式存储结构。
#define T_ERROR -1
#define T_OK 1
typedef int TStatus;
typedef int ElementType;
typedef struct BinaryNode {
ElementType data;
struct BinaryNode *leftChild, *rightChild;
} BinaryNode, *BinaryTree;
下面我们通过一个示例，来看看二叉排序树的操作。首先，我们把集合{62,88,58,47,35,73,51,99,37,93}按照二叉排序的规则生成一棵树。结果如下：
二叉排序树.png
二叉排序树的查找
在二叉排序树中查找数据可以使用递归来实现，首先我们将与根结点比较，如果小于根结点的值就去左子树中查找，如果大于根结点的值就去右子树中查找。以此类推，即可得到结果。
代码如下：
/// 二叉排序树查找
/// @param bTree 需要查找的二叉树
/// @param key 查找的key
/// @param pTree 递归使用 指向bTree的双亲结点 初始值为NULL
/// @param sTree 查找成功即返回查找到的结点TStatus返回T_OK；查找不到则返回访问的最后一个结点TStatus返回T_ERROR
TStatus searchBinarySortTree(BinaryTree bTree, int key, BinaryTree pTree, BinaryTree *sTree) {
if (!bTree) {
// 递归到树的最后一个结点 还是没有找到
*sTree = pTree;
return T_ERROR;
} else if (key == bTree->data) {
// 查找命中
*sTree = sTree;
return T_OK;
} else if (key < bTree->data) {
// 如果key小于当前结点，则在左子树中找
return searchBinarySortTree(bTree->leftChild, key, bTree, sTree);
}
// 如果key大于当前结点，则在右子树中找
return searchBinarySortTree(bTree->rightChild, key, bTree, sTree);
}
二叉排序树的插入
在二叉排序树查找的基础上做插入就比较简单了，先判断需要插入的是否存在二叉排序树中，如果存在则不能插入。如果不存在，判断是否是空树，若是空树，则把插入的结点作为根结点；如果不为空树，则只需要比较返回的结点值和
的大小，
若小于返回的结点值，则插入返回结点的左子树；
若大于返回的结点值，则插入返回结点的右子树。
代码如下：
/// 二叉排序树插入
/// @param bTree 二叉排序树
/// @param key 二叉排序树插入的key
TStatus insertBinarySortTree(BinaryTree *bTree, int key) {
BinaryTree sTree;
if (searchBinarySortTree(*bTree, key, NULL, &sTree) == T_ERROR) {
// 没有从二叉排序树中查找到当前key
BinaryTree iTree = (BinaryTree)malloc(sizeof(BinaryNode));
iTree->data = key;
iTree->leftChild = iTree->rightChild = NULL;
if (sTree == NULL) {
// 二叉树是空树
*bTree = iTree;
} else if (key < sTree->data) {
// 不是空树 key比最后一个结点的值小 往最后一个结点的左子树插入
sTree->leftChild = iTree;
} else {
// 不是空树 key比最后一个结点的值大 往最后一个结点的右子树插入
sTree->rightChild = iTree;
}
return T_OK;
}
return T_ERROR;
}
二叉排序树的删除
相对于查找和插入，二叉排序树的删除就比较麻烦了，因为删除了结点之后，我们还得必须让剩下的树还得是二叉排序树。所以我们需要对删除的结点进行分类：
- 删除的结点为叶子结点。可以直接删除不会对树造成影响。
- 删除的结点只有左子树或者只有右子树。那我们就需要将子树替换原来的结点。
- 删除的结点左右子树都有。我们先找到要删除的结点的前驱结点，然后用前驱结点来替换需要删除的结点，最后再删除前驱结点即可?；蛘哒业奖簧境岬愕暮蠹探岬?，然后使用后继结点替换被删除的结点，然后删除后继结点。
下面我们实现以下使用前驱结点删除的代码：
/// 删除结点bTree
void delete(BinaryTree *bTree) {
BinaryTree tmpTree;
if ((*bTree)->rightChild == NULL) {
// 右子树为空 对接左子树
tmpTree = *bTree;
*bTree = (*bTree)->leftChild;
free(tmpTree);
} else if ((*bTree)->leftChild == NULL) {
// 左子树为空 对接右子树
tmpTree = *bTree;
*bTree = (*bTree)->rightChild;
free(tmpTree);
} else {
// 左右子树均不为空 都需要处理
tmpTree = *bTree;
// 找待删除结点的前驱
// 找到被删除结点的左子树
BinaryTree preTree = (*bTree)->leftChild;
// 循环一直取左子树的右子树 最后一个右子树即为被删除结点的前驱结点
while (preTree->rightChild) {
tmpTree = preTree;
preTree = preTree->rightChild;
}
// 循环之后preTree没有右子树了
// tmpTree此时成了preTree的双亲结点 preTree是其右子树
// 将被删除结点替换成前驱结点
// 将被删结点的数据换成前驱的数据
(*bTree)->data = preTree->data;
if (tmpTree != *bTree) {
// preTree的值赋给了要删除的结点 所以我们需要把preTree删掉 连接tmpTree右子树
tmpTree->rightChild = preTree->leftChild;
} else {
// 连接tmpTree左子树
tmpTree->leftChild = preTree->leftChild;
}
free(preTree);
}
}
TStatus deleteBinarySortTree(BinaryTree *bTree, int key) {
if (bTree == NULL) {
return T_ERROR;
}
// 查找到要删除的key就删除对应的结点
if (key == (*bTree)->data) {
delete(bTree);
return T_OK;
} else if (key < (*bTree)->data) {
return deleteBinarySortTree(&(*bTree)->leftChild, key);
} else {
return deleteBinarySortTree(&(*bTree)->rightChild, key);
}
}
二叉排序树的操作依赖于树的形状，如果二叉排序树是平衡的，则其操作的时间复杂度为，如果是斜树的话，时间复杂度就是
。
