浅析二分搜索树的数据结构的实现（Java 实现）

[toc] # 树结构简介 - 在线性数据结构中，数据都是排成一排存放的；而树结构则是非线性的，存储在其中的数据是按分支关系组织起来的结构，就像自然界中的树那样。如下图所示：  - 从图可以看出树结构是有一种层次感的，每一个点可以有多个分支，这种组织结构是非常有优势的，简单来说树结构本身是一种天然的组织结构。 - 对于这种组织结构，日常生活中是非常常见的，比如电脑磁盘中的文件夹、公司中的人员组织结构、家族的族谱等等，如以下几图所示：    - 除了组织数据，使用树结构存储数据时，在某些情况下，处理数据是十分高效的。而我们就可以针对各种特殊情况去设计出各情况适合的高效率的树结构。 - 举个例子：比如对于查找一个数据，在线性结构中如果不知道具体位置的话需要在一堆数据里一个一个地去寻找；而对于树结构，因为树结构分支的形式，各个数据可以存在不同的分支中，在查找时就可以依据这些分支快速地找到想要的数据。 - 比如，磁盘中不同的文件夹存放不同的文件，我们在查找一个文件时，就可以根据文件夹名称去找到想要的文件。 - 以上就是树结构的一些特点的简单介绍，接下来就开始分析一下树结构中的二分搜索树的基础知识以及实现出这个数据结构的一些常用操作。 --- # 二分搜索树的基础知识 ## 二叉树的基本概念 - 在了解二分搜索树之前，需要先了解二叉树的基本概念，因为二分搜索树是基于二叉树的。实际上，二叉树是树结构中最常见的树结构，也是树结构中最为基础的结构。 - 对于二叉树，和链表一样，也是一种动态的数据结构，用户不需要担心容量的问题，设计者也不需要手动地设计动态伸缩容量的方法。 - 同时，二叉树也是由一个一个节点组成的，而对于其中的每一个节点，除了存储数据之外，还需要有两个子节点，分别指向这个节点的左节点和右节点（也称为左孩子和右孩子）。 - 此外，二叉树还具有以下特性: 1. 二叉树具有唯一根节点。 2. 二叉树每个节点最多有两个孩子。 3. 二叉树中没有孩子的节点称为叶子节点。 4. 二叉树每个节点最多只有一个父亲节点。 5. 二叉树具有天然的递归结构: 1. 每个节点的左子树也是二叉树。（每个节点的左节点是左子树的根节点） 2. 每个节点的右子树也是二叉树。（每个节点的右节点是右子树的根节点） 6. 二叉树不一定是满的: 1. 一个节点也是二叉树。（左右孩子为空） 2. NULL（空）也是二叉树。 - 以上特性归纳为图片表示如下:  - 二叉树的几种常见形态 1. 空二叉树  2. 只有一个节点的二叉树  3. 只有左节点的二叉树  4. 只有右节点的二叉树  5. 完全二叉树  6. 满二叉树  ## 二分搜索树的基本概念 - 在了解了以上二叉树的基本概念之后，那么对于二分搜索树就不需要再了解以上概念了，因为二分搜索树就是一棵二叉树，只不过它有属于它自己的一些特性。 - 对于二分搜索树，它具有以下特性: 1. 二分搜索树的每个节点的值大于其左子树的所有节点的值。 2. 二分搜索树的每个节点的值小于其右子树的所有节点的值。 3. 二分搜索树的每一棵子树也是二分搜索树。 4. 二分搜索树存储的元素必须有可比较性。 - 二分搜索树图示  ## 二分搜索树的基本结构代码实现 - 综上以上基本概念，可设计二分搜索树的基本结构的代码如下: ```java /** * 二分搜索树数据结构实现类 * 支持具有可比较性的泛型 * * @author 踏雪彡寻梅 * @date 2020/3/2 - 23:05 */ public class BST