二叉排序树的概念

二叉排序树（Binary Sort Tree），又称为二叉查找树，是一种结点值之间具有一定数量级次序的二叉树，具有以下性质：

若其左子树存在，则其左子树中每个结点的值都不大于该结点的值。
若其右子树存在，则其右子树中每个结点的值都不小于该结点的值。
若其左右子树都存在，则分别为二叉排序树。

如图1是一棵二叉排序树：

图1 二叉排序树

从二叉排序树结构中可以看出，查询每个结点需要的比较次数为结点高度加1。查找结点值“3”，需要比较两次；查找结点值“0“，需要比较四次。因此整棵树的高度越低，结点的查询复杂度越低。

二叉排序的极端情况

二叉排序树是一棵完全二叉树，如图1就是完全二叉树，其查找复杂度为。

二叉排序树的每一层只有一个结点，如图：

图2 单结点的二叉排序树

此时二叉排序树退化成链表查询，查询复杂度为。

二叉排序树的插入

【算法步骤】

若二叉排序树为空，则创建新结点作为根结点，根结点值为key。
若二叉排序树非空，则需要将key与根结点值比较：

a. 若key等于Tree->data，则无需操作。

b. 若key小于Tree->data，则将key插入左子树。

c. 若key大于Tree->data，则将key插入右子树。

【算法代码】

BiTree BSTInsert(BiTree& Tree, ElemType key)
{
  if (nullptr == Tree) /*空树或者遍历到叶子结点*/
  {
    Tree = (BiTNode*)malloc(sizeof(BiTNode));
    Tree->data = key;
    Tree->lchild = nullptr;
    Tree->rchild = nullptr;
  }
  else if (Tree->data > key)/*如果key小于当前结点的值，则插入左结点*/
  {
    Tree->lchild = BSTInsert(Tree->lchild, key);
  }
  else if (Tree->data < key)/*如果key大于当前结点的值，则插入右结点*/
  {
    Tree->rchild = BSTInsert(Tree->rchild, key);
  }
  return Tree;
}

例如，假设原二叉排序树为空树，对一组数据 {3，5，7，2，1} 做查找以及插入操作时，可以构建出一个含有表中所有关键字的二叉排序树，过程如图3所示:

图3 二叉排序树插入过程

二叉排序树的查找

【算法步骤】

若二叉排序树为空，返回空指针。
若key等于Tree->data，则查找成功，返回结点地址。
若key小于Tree->data，则递归查找左子树。
若key大于Tree->data，则递归查找右子树。

【算法代码】

BiTree Find(BiTree Tree, ElemType key)
{
  if (nullptr == Tree)
  {
    return nullptr;
  }
  else if (Tree->data > key) /*查找左子树*/
  {
    return Find(Tree->lchild, key);
  }
  else if (Tree->data < key) /*查找右子树*/
  {
    return Find(Tree->rchild, key);
  }
  else/*查找的key*/
  {
    return Tree;
  }
}

单个结点的插入和查询复杂度为。

二叉排序树的删除

二叉排序树的结点删除包括两个过程，查找和删除。结点的删除有以下三种情况：

待删除结点度为0。
待删除结点度为1。
待删除结点度为2。

【场景1】

第一种情况如下图4所示，待删除节点值为 “6”，该结点无子树，删除后并不影响二叉排序树的结构特性，可以直接删除。即二叉排序树中待删除结点度为零时，该结点为叶子结点，可以直接删除：

图4 单结点度为0

【场景2】

第二种情况如下图5所示，待删除结点值为“7”，该结点有一个左子树，删除结点后，为了维持二叉排序树结构特性，需要将左子树“上移”到删除的结点位置上，即二叉排序树中待删除的结点度为1时；可以将待删除结点的左子树或右子树“上移”到删除结点位置上，以此来满足二叉排序树的结构特性。

图5 单结点度为1

【场景3】

第三种情况如下图6所示，待删除的结点值为 “9”，该结点既有左子树，也有右子树，删除结点后，为了维持二叉排序树的结构特性，需要从其左子树中选出一个最大值的结点，“上移”到删除的结点位置上。即二叉排序树中待删除结点的度为2时，可以将待删除结点的左子树中的最大值结点“移动”到删除结点位置上，以此来满足二叉排序树的结构特性。操作过程：

查找出左子树中的最大值结点。

替换待删除结点node的值为的值。

删除结点。

因为为左子树的最大值结点，所以结点的度一定是0或1，所以删除结点的情况就转移为场景1和2两种情况。

图6 单结点度为2

单个结点的删除复杂度为。

【算法代码】

BiTree BSTDelete(BiTree& Tree, ElemType key)
{
  if (nullptr == Tree)
  {
    return nullptr;
  }
  else if (Tree->data > key)/*在该结点左子树查找结点key*/
  {
    Tree->lchild = BSTDelete(Tree->lchild, key);
  }
  else if (Tree->data < key)/*在该结点右子树查找结点key*/
  {
    Tree->rchild = BSTDelete(Tree->rchild, key);
  }
  else /*找到结点key*/
  {
    if (Tree->lchild && Tree->rchild) /*同时拥有左右子树*/
    {
      /*找到左子树最大值*/
      BiTNode* Max = FindMax(Tree->lchild);/*左子树找到最大值结点*/
      Tree->data = Max->data;/*用左子树最大值替换当前结点值*/
      Tree->lchild = BSTDelete(Tree->lchild, Max->data);/*删除左子树最大值结点*/
    }
    else if (!Tree->lchild && Tree->rchild) /*只有右子树*/
    {
      BiTNode* Node = Tree;
      Tree = Tree->rchild;
      free(Node);
    }
    else if (Tree->lchild && !Tree->rchild) /*只有左子树*/
    {
      BiTNode* Node = Tree;
      Tree = Tree->lchild;
      free(Node);
    }
    else /*没有左右子树*/
    {
      free(Tree);
      Tree = nullptr;
    }
  }
  return Tree;
}

二叉排序树查找最小值

二叉排序树的最小值在左子树，最小值结点的度一定是0或1。图1中最小值为0。

【算法代码】

BiTree FindMin(BiTree Tree)
{
  if (nullptr == Tree)
  {
    return nullptr;
  }
  else if (nullptr == Tree->lchild)
  {
    return Tree;
  }
  else
  {
    return FindMin(Tree->lchild);
  }
}

二叉排序树查找最大值

二叉排序树的最大值在右子树，最大值结点的度一定是0或1。图1中最大值为9。

【算法代码】

BiTree FindMax(BiTree Tree)
{
  if (nullptr == Tree)
  {
    return nullptr;
  }
  else if (nullptr == Tree->rchild)
  {
    return Tree;
  }
  else
  {
    return FindMax(Tree->rchild);
  }
}

Docker 入门教程 (runoob 菜鸟，从入门实战到精通)