之前的文章我们讲了二分搜索树插入、查找、深度优先遍历，以及广度优先遍历，今天我们讲二分搜索树中最难的部分——删除。删除的方法我们会分两个方面来讲，一个是删除最大值和最小值的节点，一个是删除任意一个节点。好，下面我们开始。

删除最大值和最小值

要想删除最大值和最小值，你就要先找到最大值和最小值，那如何找到最大值和最小值呢？其实，只要你仔细看了上面的文章，寻找最大值和最小值还是比较简单的。寻找最大值，只要沿着二叉树的右子树一直找下去，直到当前节点没有右孩子的时候，这个节点就是二叉树中的最大值。寻找最小值，只要沿着二叉树的左子树一直找下去，直到当前节点没有左孩子的时候，这个节点就是二叉树中的最小值。源码实现起来也是非常简单，见下图：

删除最小值的源码

找到最大值和最小值是很简单，那删除简单吗？我们看下面这棵二叉搜索树（见下图）：

删除最小值的初始树

假设我们删除这棵二叉搜索树中的最小值，从图中可以看出来，删除13这个节点，很简单，直接删除就可以了。然后再删除最小值呢？删除14这个节点也很简单，直接删除就可以了。然后再删除最小值呢？直接删除18节点还可以吗？当然不可以了，如果直接删除18节点，该节点的右子树就丢失了。所以说，在删除最小值的时候，最关键的就是当最小值节点有右子树的时候该如何进行操作。

其实操作也很简单，直接把当前待删除节点的右子树挂到当前节点的父节点上就可以了。效果见下图：

删除最小值的过程

操作确实是很简单，源码该怎么实现呢？源码如下图所示：

删除最小值的源码

通过讲解最小值的删除图示和源码，希望您能够把最大值删除的操作示意以及源码能够编写出来，相信对于您来说只要理解了上面的内容，应该不是难事。

好，讲到这里，聪明的您也许能够发现，其实不管是删除最大值还是删除最小值，待删除节点都有一个特点，就是只有一个子树。也就是说对于删除只有一棵子树的节点，删除算法也还是比较简单的。但有两颗子树的节点该如何删除呢，这就是我们下面要重点讲的Hubbard删除法。

Hubbard删除法

如下图所示，我想删除55这个节点，这个节点是既有左子树，又有右子树，该如何删除呢？

删除普通节点示意图

最关键的是找到一个节点代替55，该找哪个节点呢？答案是：找55的后继节点。所谓后继节点就是在这个二叉查找树中，比55大的节点中，最小的那一个（对应的还有前驱节点）。在上面的图示中，也就是57那个节点。那找到之后该如何删除呢？具体的算法如下：

1）将57上移，然后57的右子树挂接到57的父节点上（其实就是删除只有一棵子树的情况）；

2）将57这个节点分别指向待删除节点的左右子树；

3）删除55这个节点；

具体演示过程，如下图所示：

删除普通节点的过程

演示过程看起来也不是很难，代码实现起来其实也不难，只要你明白了二叉查找树的递归性质，掌握了删除最大值和最小值的方法，源码写起来也应该是无需费多大力气。大致的实现逻辑如下：

1）如果无法找到待删除节点，直接返回NULL；

2）如果待删除节点的key值比当前节点小，那递归调用自身函数，将当前节点的左子树传入进去；

3）如果待删除节点的key值比当前节点大，那递归调用自身函数，将当前节点的右子树传入进去；

4）如果待删除节点的key值等于当前节点，那就是要删除当前节点，继续分三步：

一是：如果当前节点没有左子树，则使用删除最小值的方法；

二是：如果当前节点没有右子树，则使用删除最大值的方法；

三是：如果当前节点左右子树都存在，那就是找这个节点的后继节点，然后使用上面我们提到的方法；

具体的源码实现如下图所示：

删除源码

通过观察删除最小值和删除任意一个节点的源码，不知您有没有发现一个问题，就是这两个函数都没有返回是否删除成功。那您能不能想想，这个是否删除成功的标志应不应该加呢，如果需要加，那加在那里最好呢？欢迎您在文章的下发评论留言。

我是徐建航，这是我写的第74篇文章，欢迎你加入007社群，七天写一篇，一起写七年，七年之后一起去南极。