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

接下来我们就要实现要删除的结点有两个子节点的情况，这种情况上面我们已经分析过了，实现起来并不复杂。下方这个deleteNoteHaveTwoChild()方法就是删除有两个子节点的情况，该方法的参数是查找的我们要删除的结点的查找结果。其实就是查找，替换和删除三个步骤。下方代码可以分为以下几步：

首先初始化将被删除的结点的右子树的最左边结点的查找结果对象。

然后便利要删除结点的右子树，找到右子树上最左边的结点，也是右子书上最小的那个结点，并将相应信息存储到我们的查找结果对象中。

将右子树中最小的值赋值给我们要删除的结点，然后调用上面的方法将该右子树上的最小结点删除即可。

三、测试用例

经过上的所有步骤，我们的二叉排序树的查找、插入、删除实现完毕。接下来又到了测试的时间了，下方就是我们本篇博客的测试用例。首先我们通过线性表来创建二叉排序，如何依次删除99，35，37，62这些节点，这些节点有叶子节点，有的只有左子树，有的也只有右子树，有的既有左子树也有右子树。

上述代码的输出结果为，从最后一个输出结果我们可以看出，我们要删除的结点62既有左子树也有右子树，所以寻找62右子树上最小的值73，然后将62进行覆盖。最后把62右子树上的73进行释放掉即可。

本篇博客只对二叉排序树的核心代码进行了介绍，完整示例请移步github, 本篇博客中所有代码都会在github上进行分享，分享地址如下所示：

github分享地址：https://github.com/lizelu/DataStruct-Swift/tree/master/BinarySearchTree

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