二分搜索树的原理与Java源码实现( 二 )

文章图片
代码实现分别如下：

文章图片

文章图片
其中层序遍历就是一层一层的从左到右遍历上图中层序遍历的结果是13615371018代码实现需要借助队列，代码实现如下：
文章图片
2.4二叉搜索树的删除
二叉搜索树最麻烦的就是删除节点，删除任意二叉树中的节点之前，我们来先删除特殊的节点。
删除二叉搜索树中最小的节点
更多内容↓↓↓删除二叉搜索树中最大的节点
查找二叉搜索树中最小的节点
查找二叉搜索树中最大的节点
我们先来实现这些操作。
如下图

文章图片
根据二叉搜索树的定义，可以得出以下结论
在一个二叉搜索树中，最小的节点一定是最左边的节点，也就是图中的节点3
在一个二叉搜索树中，最大的节点一定是最右边的节点，也就是图中的节点18
总之：最小节点去左子树中找，直到节点的左孩子为空，则当前节点就是最小节点最大节点去右子树中找，直到节点的右孩子为空，则当前节点就是最大节点
1先来实现查找二叉搜索树中最小的节点如下代码

文章图片
同理，查找最大节点也是一样2实现查找二叉搜索树中最大的节点代码如下：

文章图片
上面实现了查找最小节点和最大节点，下面我们再来实现删除最小节点和删除最大节点
3实现删除二叉搜索树中最小的节点一直往左孩子中删除，当某一个节点node没有左孩子时，说明当前节点就是最小节点这时候分两种情况
当前节点有右孩子如果是这种情况，直接把右孩子返回，作为当前节点
当前节点没有右孩子如果是这种情况，直接返回null 。此时返回右孩子也行，因为右孩子也是null
代码实现如下

文章图片
同理，删除二叉搜索树中最大的节点的代码如下：

文章图片
下面来分析一下删除任意一个节点。删除任意一个节点node ，那么可以分为以下几种情况
node没有孩子
node只有一个孩子
node有两个孩子
更多内容↓↓↓如下图一棵二叉搜索树，我们来分析

文章图片
第一种情况：node没有孩子这种情况最简单，直接删除就行了，剩下的还是一棵二叉搜索树比如图中的节点5 ，节点13 ，节点27 ，节点50 ，删除任意一个节点之后剩下的还是满足一棵二叉搜索树第二种情况：node只有一个孩子这种情况又分两种
上面两种情况其实不影响，比如图中的节点10 ，节点45,分别有一个左孩子和一个右孩子。也好办，节点10删除后，它的左孩子节点5 ，放在节点10的位置同理知，节点45删除后，它的右孩子节点50 ，放在节点45的位置这样一来，剩下的节点还是一棵二叉搜索树第三种情况：node有两个孩子还是上图为准，以节点17为例，节点17有左右两个孩子,分别是10 ， 19要删除节点17 ，怎么办呢？或者说节点17删除后，哪个节点应该放在节点17的位置上呢？我们节点17满足两个性质：【