计算机考研的考生们注意啦，下面是计算机考研数据结构之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)所示。

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