二叉排序树（BST）

二叉排序树的定义

Q：什么是二叉排序树

A：二叉排序树或者是一棵空树，或者是具有如下性质的二叉树

1）若它的左子树不空，则 左子树 上所有结点的值 均小于 它的根结点的值

2）若它的右子树不空，则 右子树 上所有结点的值 均大于 它的根结点的值

3）左、右子树也分别是一棵二叉排序树

一棵二叉排序树

二叉排序树的操作

二叉排序树的查找

二叉排序树的查找是从根结点开始，沿某个分支逐层向下比较的过程。若二叉排序树为空，先将给定值与根结点的关键字比较，若相等，则查找成功。若不相等，如果小于根结点的关键字，则在根结点的左子树上查找，如果大于根结点的关键字，则在根结点的右子树上查找。

我们在下图中查找值为 4 的结点

第一步：找到根结点 6

第二步：4 与根结点 6 比较。由于 4 小于 6 ，根据定义，我们在根结点 6 的左子树继续查找，此时根结点为 2

第三步：4 与根结点 2 比较。由于 4 大于 2 ，根据定义，我们在根结点 2 的右子树继续查找，此时根结点为 4

第四步：查找成功！

代码演示

通过上文图片讲解，很显然，二叉排序树的查找是一个递归的过程

下面是二叉排序树的递归查找算法：

BSTNode* BSTree_search(BSTNode* node, int key)
{
    if (node == NULL || node->key == key)
        return node;
    if (node->key < key)
         BSTree_search(node->right, key);
    else BSTree_search(node->left, key);
}

二叉排序树的插入

二叉排序树的插入原理和上面的查找操作类似：若原二叉排序树为空，则直接插入结点，否则，若关键字 k 小于根结点，则插入到左子树，若关键字 k 大于根结点值，则插入到右子树。插入的结点一定是一个新添加的叶结点，且是查找失败时的查找路径上访问的最后一个结点的左孩子或者右孩子。

我们在下图中插入值为 5 的结点

第一步：找到根结点 6

第二步：5 与根结点 6 比较。由于 5 小于 6 ，根据定义，我们要插入到根结点 6 的左子树当中，此时根结点为 2

第三步：5 与根结点 2 比较。由于 5 大于 2 ，根据定义，我们要插入到根结点 2 的右子树当中，此时根结点为 4

第四步：5 与根结点 4 比较。由于 5 大于 4 ，根据定义，我们要插入到根结点 4 的右子树当中，访问结点 4 的右孩子，发现为空，则将 5 作为 4 号结点的右孩子插入。

代码演示

下面是二叉排序树的插入算法：

int BST_Insert(BiTree &T,KeyType k)
{
  if(T==NULL)   //原树为空，新插入的记录为根结点
  {
  T=(BiTree)malloc(sizeof(BSTNode));
  T->key=k; 
  T->lchild=t->rchild=NULL;
  return 1;  //返回 1，插入成功 
  } 
  else if(k==T->key)  //树中存在相同关键字的结点，插入失败
  return 0;
  else if(k<->key)  //插入到 T 的左子树 
  return  BST_Insert(T->lchild,k);
  else    //插入到 T 的右子树 
  return  BST_Insert(T->rchild,k);
}

二叉排序树的构造

二叉排序树的构建从一棵空树出发，依次输入元素，把他们插入到二叉排序树的合适位置。

代码演示

下面是二叉排序树的构建算法：

void Creat_BST(BiTree &T,KeyType str[],int n)
{
  T=NULL;    //初始时 T 为空树 
  int i=0;
  while(i<n){   //依次将每个关键字插入到二叉排序树中 
  BST_Insert(T,str[i]) ;
  i++;
  }
}

二叉排序树的删除

在二叉排序树中删除一个结点时，不能直接把以该结点为根的子树上的结点都删除，必须先把被删除结点从存储二叉排序树的链表中摘下来，将因删除结点而断开的二叉链表重新链接起来，同时要确保二叉排序树的性质不会丢失。

一般来说，删除操作的实现有三种情况。

1）若被删除结点 z 是叶结点，则直接删除，不会破坏二叉排序树的性质

举例：删除结点 5

结点 5 是叶结点，可以直接删除

2）若结点 z 只有一棵左子树或右子树，则让 z 的子树成为 z 父结点的子树，替换 z 的位置

举例：删除结点 4

结点 4 只有一棵左子树，让结点 2 成为结点 2 的子树

3）若结点 z 有左、右两棵子树，我们可以在该节点的左子树去寻找最大的结点或者在右子树去寻找最小的结点，然后交换两者，将交换的左子树最大结点或者右子树最小的结点进行删除，这样就转换成了第一或第二种情况。

举例：删除结点 2

第一步：我们找到该结点右子树最小的结点，也就是结点 3，然后交换两者

第二步：删除最小结点