说在前头:本人为大二在读学生,书写文章的目的是为了对自己掌握的知识和技术进行一定的记录,同时乐于与大家一起分享,因本人资历尚浅,能力有限,文章难免存在一些错漏之处,还请阅读此文章的大牛们见谅与斧正。若在阅读时有任何的问题,也可通过评论提出,本人将根据自身能力对问题进行一定的解答。
前言
—
在前面的文章中,我们知道了,有序数组结构在查找某个指定的数据时要比链表结构快,时间复杂度为O(log2N),但插入数据不如链表,复杂度为O(N)。而链表查找数据的时间复杂度为O(N),插入和删除数据时间复杂度为O(1)。
我们可以展开一下思考,有没有那么一种数据结构可以同时满足有序的快查询和链表的快插入?答案是肯定的,这也是本篇文章的重点——二叉树结构。
二叉树结构的概念:一棵树由多个节点组成,其中最上层的节点称为根节点,连接在其下面的的两个节点为其子节点(左节点,右节点),根节点为这两个子节点的父节点。对于没有子节点的节点我们称为叶子节点。
对于二叉树有许多实现方式,本篇文章我们将来探讨二叉搜索树结构,准备好,要发车咯!
01
—
算法思想
二叉搜索树的特点是,一个节点的左子节点的关键字值小于这个节点,右子节点的关键字值大于或等于这个父节点。(如下图)
在上面的图中,根节点为5,根节点的左右节点分别是3和7,而3的左右节点又为2和4;2,4,6,8都为叶子节点。
通过观察我们不难发现,左子节点总是小于父节点,而右子节点总是大于或等于父节点,这一规则保证了二叉树中数据的有序性。
02
—
非平衡树
上面展示的二叉树属于一颗理想的二叉搜索树,非常的对称。但在实际的运用中,二叉搜索数并非可以一直保持这种理想的状态(如下图)
这是由于数据插入时的顺序造成的,当数据较为随机时,结构会更趋于平衡的理想结构,但当数据较为有序时,就会出现上述的情况,最坏的情况可能使树结构退化成链表结构(如下图)
按顺序插入1,2,3,4,5时,这种结构的树从严格意义上已经不能再称得上是树结构了,因为其已经退化成了链表结构,失去了二叉搜索树的优势和特点。介于本文主要介绍二叉搜索树的实现和具体代码实现,对于这种退化情况的处理,我们将会在后面的文章进行详细的讲解,本文不做深入的探讨。
接下来我们将分步使用代码实现二叉搜索树。
03
—
创建节点类Node
每棵树都由多个节点构成,节点主要用于保存每个数据的值以及数据之间的关系,因此,节点类Node至少需要存在以下三个成员变量:左节点,数据的值,右节点(leftNode,value,rightNode),具体代码参考如下
Node.java
package