二叉排序树的查找_二叉排序树的查找长度_二叉排序树的查找方法(3)

二、二叉排序树结点的删除

二叉排序树的结点删除要比二叉排序树结点的插入要复杂一些，不过也并不难，要分为几种情况进行讨论。二叉排序树结点的插入与删除都是在查找的基础上来做的。下方我们就假设找到了我们要删除的结点，根据结点含有的左右结点的个数来进行分类讨论。下方会对这几种情况进行讨论。

1.删除结点的几种情况

(1)、删除结点为叶子结点

删除的结点没有左子树也没有右子树，也就是删除的结点为叶子结点。这种情况下我们有可以细分为两类，一种是该叶子结点就是二叉排序树的根节点，也就是二叉排序树中只有一个节点的情况。只需要将root指针置为空即可。再一种情况是有删除的叶子节点有父节点，直接将父节点连接该删除节点的指针置空即可。如下所示：

(2)、删除的节点只有左子树的情况

该情况也可以细分为两类，一种是该删除的结点没有父节点，也就删除的节点为根节点，我们需要将根节点的root指针指向即将删除结点的左孩子，然后将删除结点的leftChild置空即可。

如果该结点有父节点，那么将父节点相应的孩子指针指向删除节点的左孩子，然后将删除节点的leftChild置空。如下所示：

(3)、删除的节点只有右子树的情况

该情况也可以细分为两类，一种是该删除的结点没有父节点，也就删除的节点为根节点，我们需要将根节点的root指针指向即将删除结点的右孩子，然后将删除结点的rightChild置空即可。

如果该结点有父节点，那么将父节点相应的孩子指针指向删除节点的右孩子，然后将删除节点的rightChild置空。如下所示：

(4)、删除的节点既有左子树也有右子树的情况

这种情况会稍微复杂一些，我们采用覆盖，再删除的方式进行解决。也就是曲线解决。直接将有左子树也有右子树的结点干掉似乎不是很好实现，因为这样会破坏二叉排序树的结果。我们可以间接的去做。可以分为下方的两步。

第一步：查找删除结点右子树中最小的那个值，也就是右子树中位于最左方的那个结点。然后将这个结点的值的父节点记录下来。并且将该节点的值赋给我们要删除的结点。也就是覆盖。

第二步：然后将右子树中最小的那个结点进行删除，该节点肯定符合上述三种情况的某一种情况，所以可以使用上述的方法进行删除。

这样一来我们就间接的删除了既有左子树也有右子树的结点。具体如下所示

2.删除结点的代码实现

接下来我们要根据上述的示例图来实现我们的代码。上述将删除的结点分为了四类，其实仔细分析一下，上面的前三种删除结点的情况类似。于是乎我们在代码实现时将前三种删除结点的方法归为一类处理，也就是封装成一个函数来删除有一个或者没有子结点类型的结点。下方的deleteNoteHaveZeroOrOneChild()函数就是相应的方法。该函数有两个参数，第一个就是我们查找到要删除结点的查找结果对象，第二个参数就是该节点的子节点，如果该节点没有子节点的话，那么该参数就为nil。

在下方函数代码中，大体可以分为以下几步：

首先调用setNilForNote()方法将该将要删除的结点的子节点指针置空

然后判断此将要被删除的结点是否是二叉排序树的根节点，如果是的话，就使rootNote指针指向该结点的子结点。

如果要被删除的结点不为根节点的话，我们需要判断要删除结点的值是比其父节点的值是大还是小，如果是小的话，说明要删除的结点是其父节点的左孩子，然后就要把父节点的leftChild指针指向要删除结点的子节点。同理如果删除结点的值要比父节点的值要大，那么就需要将父节点的rightChild指针指向删除结点的子结点。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25279-3.html