无名阁,只为技术而生。流水不争先,争的是滔滔不绝。

数据结构:二叉排序树的构造过程(图文详解)

前沿技术 dancy 1年前 (2023-11-23) 228次浏览 已收录 0个评论 扫描二维码

二叉排序树的概念

二叉排序树(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 菜鸟,从入门实战到精通)

喜欢 (0)
[]
分享 (0)
关于作者:
发表我的评论
取消评论

评论审核已启用。您的评论可能需要一段时间后才能被显示。

表情 贴图 加粗 删除线 居中 斜体 签到