计算机考研考点解析:数据结构之BST树 (下)

计算机考研的考生们注意啦,下面是计算机考研数据结构之BST树的相关介绍,包括BST树的定义和性质等知识点,各位考生要认真复习,预祝大家能够取得好成绩。

3、删除

在二叉排序树中删除一个结点时,必须确保删除结点后的二叉排序树仍满足二叉排序树的定义。删除操作的实现过程按以下三种情况来处理:

(1)如果被删除结点x是叶结点,则直接删除。

(2)若结点x只有一棵左子树或右子树,则让x的子树成为x父结点的子树,替代x的位置。

(3)若结点x有左、右两棵子树,则令x的中序后继(或前驱)替 代x,然后从二叉排序树中删去这个直接后继(或直接前驱),这样就转换成了第一种或第二种情况。

我们通过一个图来讲解删除的情形,大家只需要掌握如何删除就可以,代码不用掌握。

设被删除结点为p,其父结点为f ,删除情况如下:

若p是叶子结点: 直接删除p,如图(a)和(b)所示。
计算机考研考点解析

若p只有一棵子树,在图(c)中只有左子树:直接用p的左子树取代p的位置而成为f的一棵子树。即原来p是f的左子树,则p的子树成为f的左子树,如图(f)。
计算机考研考点解析

若p只有一棵子树,在图(e)中p是f的右子树,直接用p的右子树取代p的位置而成为f的一棵子树。即原来p是f的右子树,则p的子树成为f的右子树,则p的子树成为f的右子树,如图(f)所示
计算机考研考点解析

若p既有左子树又有右子树 :处理方法有以下两种,可以任选其中一种。

①用p的直接前驱结点代替p。在图(g)中删除12,12具有左子树和右子树,用12 的直接前驱10代替12,如图(h),即从p的左子树中选择值最大的结点s放在p的位置(用结点s的内容替换结点p内容),然后删除结点s。s是p的左子树中的最右边的结点且没有右子树,对s的删除同(2),如图(i)所示。
计算机考研考点解析

②用p的直接后继结点代替p。在图(j)中删除12,12具有左子树和右子树,用12 的直接后继10代替12,如图(k),即从p的左子树中选择值最大的结点s放在p的位置(用结点s的内容替换结点p内容),然后删除结点s。s是p的左子树中的最右边的结点且没有右子树,对s的删除同(3),如图(m)所示。

以上就是为大家整理的计算机考研数据结构知识点介绍,考生们在备考过程中遇到问题,可以在右侧咨询窗口留言,会有老师一对一为大家解答,助力大家顺利通过考研初试、考研复试

【23考研黄金期辅导课程推荐】23百日集训营23暑期集训营线上+线下VIP领学计划龙腾一对一专属VIP公共课+专业课全科辅导,这些课程中都会配有内部讲义以及辅导书和资料,同时会有教研教辅双师模式对大家进行教学以及督学,并配有24小时答疑和模拟测试等,具体详情可直接咨询在线客服老师。

新集训网站已上线,会不定期更新考研资讯热点信息。感兴趣的小伙伴可以点击直达新集训网站电脑端新集训网站手机端


免责声明:本平台部分帖子来源于网络整理,不对事件的真实性负责,具体考研相关内容请以各院校的官网通知为准。 如果本站文章侵犯到您的权利,请联系我们(400-108-7500)进行删帖处理。

启航教育热门私房课

MORE
  • 2023考研VIP领学计划

    时间:随报随学
    形式:网课+面授
     

    查看详情

    在线咨询

  • 2023考研全年集训营

    时间:3.1-12.16
    形式:面授
     

    查看详情

    在线咨询

  • 2023考研二战集训营

    3.1-12.16
    形式:面授
     

    查看详情

    在线咨询

姓名

手机号

报考专业

请选择  
  • 计算机
  • 经济学
  • 金融硕士
  • 法律硕士
  • 应用统计
  • 机械工程
  • 管理学
  • 通信工程
  • 教育学
  • 心理学
  • 国际商务
  • 土木工程
  • 其他专业
一键申请
扫描上方二维码免费领取学习资料