万字长文带你实现二分搜索树
什么是二叉树？
在实现二分搜索树之前，我们先思考一下，为什么要有树这种数据结构呢？我们通过企业的组织机构、文件存储、数据库索引等这些常见的应用会发现，将数据使用树结构存储后，会出奇的高效，树结构本身是一种天然的组织结构。常见的树结构有：二分搜索树、平衡二叉树（常见的平衡二叉树有AVL和红黑树）、堆、并查集、线段树、Trie等。Trie又叫字典树或前缀树。 树和链表一样，都属于动态数据结构，由于二分搜索树是二叉树的一种，我们先来说说什么是二叉树。二叉树具有唯一的根节点，二叉树每个节点最多有两个孩子节点,二叉树的每个节点最多有一个父亲节点，二叉树具有天然递归结构，每个节点的左子数也是一棵二叉树，每个节点的右子树也是一颗二叉树。二叉树如下图： 
什么是二分搜索树？
二分搜索树也是一种二叉树，但二分搜索树种每个节点的值都要大于其左子树所有节点的值，小于其右子树所有节点的值，每一棵子树也是二分搜索树。正因为二分搜索树的这种性质，二分搜索树存储的元素必须具有可比较性。下图就是一棵二分搜索树： 
我们可以根据二分搜索树的特点，构建一颗二分搜索树，代码实现如下：
二分搜索树的基本操作
二分搜索树添加新元素
我们在向二分搜索中添加元素时，需要保持二分搜索树的性质，即需要将我们添加的元素从根节点开始比较，若比根节点小，则去根节点的左子树递归进行添加操作，若比根节点的右子树递归进行添加操作，若相等，则直接返回，因为本文实现的是一棵不包含重复元素的二分搜索树。具体代码实现如下：
通过上面添加方法的代码实现中，可以看出有如下两点不足并且可以优化的地方：1.待添加元素e需要与当前节点的值进行两轮比较;2.递归终止条件太臃肿了.我们可以来简化一下上面的添加元素的方法，如下：
改进之后添加方法就简洁很多了，现在我们完成了二分搜索树的添加后，想一下如何在二分搜索中查找某个元素呢？我们可以用contains()方法来表示当前二分搜索中是否包含该元素，代码实现如下：
二分搜索树的遍历（包含非递归实现）
什么是遍历操作？
遍历操作就是把所有的节点都访问一遍，当然访问的原因和你如何访问都和你具体的业务相关，本文主要是通过在在控制台打印输出该节点的值，来完成访问的。我们知道在线性结构下，遍历是极其容易的，比如数组和链表的遍历，当然在树结构下，我们可以通过递归来使二分搜索树的遍历变得非常简单。
递归实现
前序遍历
就几行代码，我们就已经完成了我们的前序遍历，是不是很简单，我们现在可以来测试一下我们前面写的添加方法和现在的前序遍历操作，为了更好在控制台看我们的打印结果，我们需要重写一下二分搜索树的toString()，我们可以用“–”来表示节点所在的深度，让输出效果更直观，实现如下：
我们可以在主方法中添加我们的测试代码，测试代码如下：
我们现在根据上面的测试代码，来一起看下运行结果： 
我们根据运行结果画出的树结构，可以看出是满足二分搜索树的性质的，因此也证明了我们的添加方法和前序遍历是没有问题的。
中序遍历
根据我们的前序遍历的递归实现，我们可以很容易地写出二分搜索树的中序遍历，具体实现如下：
后序遍历
通过前序遍历和中序遍历的学习，我相信大家对后序遍历的递归实现已经觉得非常容易了，代码如下：
非递归实现
前序遍历
实现思路：当我们使用非递归来实现二分搜索树的前序遍历时，我们可以借助栈这种数据结构，由于栈是后进先出的，我们需要先将当前节点的右孩子压入栈中，再将当前节点的左孩子压入栈中，当我们的栈不为空时，我们就循环执行出栈操作，并且将出栈的元素作为当前节点。当然，如果你还不了解栈这种数据结构，你可以看我的上篇文章：常见的线性结构进行学习。非递归前序遍历具体代码实现如下：
中序遍历
二分搜索树中序遍历的非递归实现，这里还是通过借助栈来实现的，理解起来要比前序遍历的非递归实现复杂一些，希望大家可以认真思考，仔细体会，具体代码实现如下：
后序遍历
我们通过前面的前序遍历和中序遍历的非递归算法的实现，都是采用的栈这种数据结构进行实现，这也和我们程序调用的系统栈的工作原理相似，下面我们后序遍历的非递归算法仍然接站栈这种数据结构进行实现，这样可以帮助我们更加的熟悉栈这种数据结构的应用，具体代码实现如下：
层序遍历
层序遍历和前面三种遍历方式都不一样，前、中、后序遍历本质上都是深度优先遍历，在进行前、中、后序遍历时，会先一直走到二分搜索树的叶子节点，也就是最大深度，而我们的层序遍历，本质上是一种广度优先遍历，就是横向遍历完所有节点后，再遍历下一层节点，如下图： 
那么二分搜索树的层序遍历如何实现呢，我们前面讲过队列这种数据结构是先进先出的，我们可以将二分搜索树中的每层节点顺序放进队列中，然后再进行出队操作就可以了，若你不清楚队列，你可以看我的上篇文章常见的线性结构进行学习，现在就让我们来看是如何使用队列实现二分搜索树的层序遍历吧，具体代码实现如下：
删除二分搜索树中的元素
由于删除二分搜索中的任意元素是比较复杂的，我们可以先研究如何实现删除二分搜索树的最大值和最小值，当然我们得先找到这棵二分搜索树的最大值和最小值，查找方法如下：
现在我们已经找出最小元素和最大元素所在的节点了，我们现在就可以是实现删除最小元素和最大元素所在的节点操作了，代码如下：
在我们实现删除二分搜索树中的最大元素所在的节点和删除最小元素所在的节点操作后，我们可以写一个简单的测试用例，来验证下我们的删除最大值和删除最小值操作是否正确：
有了如上操作作为铺垫后，现在就可以来实现删除二分搜索树中的指定元素的操作了，需要注意的是，当待删除节点的左右子树都不为空时，我们需要找到待删除元素的后继或者前驱，后继就是指待删除节点右子树中最小的元素所在的节点，前驱是指待删除节点左子树最大的元素所在的节点。本文是采用的待删除节点的后继来代替待删除元素的位置。 前驱图示:待删除节点右子树中最小的元素所在的节点 
后继图示：待删除节点左子树最大的元素所在的节点 
具体代码实现如下：
本文实现的是一个不包含重复元素的二分搜索树，若你需要你的二分搜索树包含重复元素，在进行添加操作时只需要定义左子树小于等于节点；或者右子树大于等于节点。二分搜索树的学习就到这里了，希望本文能让你对二分搜索树有更深的理解。
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/92598.html
