本文篇幅较长，大约字，还请耐心读完，相信你一定会在本文中有个不错的收获，当然个人水平有限，不足之处在所难免，还请指教，同时也欢迎在评论区留言交流！谢谢！祝您阅读愉快！ps：同时文中推荐了两本好的编程书籍，欢迎大家购买阅读，限时优惠，限时优惠，显示优惠哟！
树结构简介
在线性数据结构中，数据都是排成一排存放的；而树结构则是非线性的，存储在其中的数据是按分支关系组织起来的结构，就像自然界中的树那样。如下图所示：
从图可以看出树结构是有一种层次感的，每一个点可以有多个分支，这种组织结构是非常有优势的，简单来说树结构本身是一种天然的组织结构。对于这种组织结构，日常生活中是非常常见的，比如电脑磁盘中的文件夹、公司中的人员组织结构、家族的族谱等等，如以下几图所示：
除了组织数据，使用树结构存储数据时，在某些情况下，处理数据是十分高效的。而我们就可以针对各种特殊情况去设计出各情况适合的高效率的树结构。举个例子：比如对于查找一个数据，在线性结构中如果不知道具体位置的话需要在一堆数据里一个一个地去寻找；而对于树结构，因为树结构分支的形式，各个数据可以存在不同的分支中，在查找时就可以依据这些分支快速地找到想要的数据。比如，磁盘中不同的文件夹存放不同的文件，我们在查找一个文件时，就可以根据文件夹名称去找到想要的文件。以上就是树结构的一些特点的简单介绍，接下来就开始分析一下树结构中的二分搜索树的基础知识以及实现出这个数据结构的一些常用操作。
Java语言程序设计与数据结构（基础篇）（原书第11版）京东好评率98%无理由退换京东配送官方店旗舰店￥98购买二分搜索树的基础知识
二叉树的基本概念
在了解二分搜索树之前，需要先了解二叉树的基本概念，因为二分搜索树是基于二叉树的。实际上，二叉树是树结构中最常见的树结构，也是树结构中最为基础的结构。对于二叉树，和链表一样，也是一种动态的数据结构，用户不需要担心容量的问题，设计者也不需要手动地设计动态伸缩容量的方法。同时，二叉树也是由一个一个节点组成的，而对于其中的每一个节点，除了存储数据之外，还需要有两个子节点，分别指向这个节点的左节点和右节点（也称为左孩子和右孩子）。此外，二叉树还具有以下特性:一个节点也是二叉树。（左右孩子为空）NULL（空）也是二叉树。每个节点的左子树也是二叉树。（每个节点的左节点是左子树的根节点）每个节点的右子树也是二叉树。（每个节点的右节点是右子树的根节点）二叉树具有唯一根节点。二叉树每个节点最多有两个孩子。二叉树中没有孩子的节点称为叶子节点。二叉树每个节点最多只有一个父亲节点。二叉树具有天然的递归结构:二叉树不一定是满的:以上特性归纳为图片表示如下:
二叉树的几种常见形态1.空二叉树
2.只有一个节点的二叉树
3.只有左节点的二叉树
4.只有右节点的二叉树
5.完全二叉树
6.满二叉树
二分搜索树的基本概念
在了解了以上二叉树的基本概念之后，那么对于二分搜索树就不需要再了解以上概念了，因为二分搜索树就是一棵二叉树，只不过它有属于它自己的一些特性。对于二分搜索树，它具有以下特性:二分搜索树的每个节点的值大于其左子树的所有节点的值。二分搜索树的每个节点的值小于其右子树的所有节点的值。二分搜索树的每一棵子树也是二分搜索树。二分搜索树存储的元素必须有可比较性。二分搜索树图示
二分搜索树的基本结构代码实现
综上以上基本概念，可设计二分搜索树的基本结构的代码如下:
二分搜索树的常见基本操作实现
添加操作
添加操作初步实现
对于二分搜索树的添加操作，可分为以下两种情况（为了更加简洁明了，此处使用动图表示）:1.空树时添加一个新元素:
2.树中已有元素时添加新元素:
以上就是添加元素的过程，其中需要注意的是在这里的二分搜索树的实现中，不包含重复元素，如果添加的元素已有了直接返回忽略。如果需要包含重复元素，只需要定义为：左子树小于等于父节点，右子树大于等于父节点。对于其代码实现，可以使用非递归方式也可以使用递归方式，对于非递归方式，实现步骤其实和链表比较相像；但是在树结构中，递归实现是比非递归方式简单的，所以在这里使用递归的方式来实现。不过使用递归方式也是有一定的局限性的。比如在添加元素的最坏的情况下，二分搜索树会形成一个链表（只添加左节点或右节点），这种情况下一直添加元素，由于不断地递归，递归高度越来越高，内存将会被撑爆，这一点也是需要了解的。从以上图示中，可归纳为以下步骤（递归实现）:如果添加的元素比当前节点的元素小，添加到当前节点的左子树中。如果添加的元素比当前节点的元素大，添加到当前节点的右子树中。添加的元素在树中已有，直接忽略掉返回即可。（不包含重复元素）如果添加的元素添加到某个节点的左节点中且当前这个节点的左节点为空，则将元素添加到当前这个节点的左节点中并返回回去。如果添加的元素添加到某个节点的右节点中且当前这个节点的右节点为空，则将元素添加到当前这个节点的右节点中并返回回去。添加元素前，先判断当前二分搜索树是否为空。如果为空将元素添加到根节点中；如果不为空，从根节点开始，递归将元素添加到树中。递归终止条件:如果不满足以上终止条件，进行递归添加元素:以上步骤实现为代码形式如下:
添加操作改进
在上面的添加操作实现中，在添加新元素的时候进行了两轮的比较，第一轮是在终止条件时比较，第二轮是不满足终止条件时比较，这样子看起来终止条件显得比较臃肿。而对于二叉树而言，空（null）也可以是一颗二叉树。所以可以设计为添加元素时当递归到某个节点的左节点或右节点时或者树为空时添加元素时，这个节点正好为空（null），此时就可以new一个节点将元素添加进去并返回这个节点给上一层的二分搜索树的左节点或右节点接收或者给根节点root接收，此时返回的这个节点就是一棵二分搜索树同时也是这棵树的根节点，对于相等的元素则不做处理，最后再返回递归最开始的根节点回去给上层节点或者根节点root接收即可。此时在初始调用添加操作时，就不需要再判断二分搜索树是否为空了，只需使用root接收调用结果即可。以上过程用动图表示如下:
代码改进后如下:
查询操作
对于二分搜索树的查询操作，这里实现一个contains方法用于判断要查找的元素是否存在于二分搜索树中，如果存在返回true，如果不存在返回false。对于这个操作的实现步骤如下（递归实现）:首先判断当前递归到的根节点是否为空，如果为空则说明当前递归到的树没有元素，返回false。接着判断当前递归到的根节点中的元素是否为要查找的元素，如果是则返回true，否则进行后续的判断。对于剩下的判断则是判断要查找的元素是大于还是小于当前递归到的根节点，大于就在右子树中继续寻找，小于则在左子树中继续寻找，接着继续以上1、2、3步的操作，直至出现结果为止。此操作实现代码为下:
遍历操作
对于遍历，这个操作是十分常见的。在二分搜索树中，遍历操作就是把所有的节点都访问一遍。在前面的线性结构中，遍历是及其容易的，使用循环就行了。不过在树结构中遍历也比线性结构难不了多少，也是比较简单的。在树结构中有这么几种遍历：前序遍历、中序遍历、后序遍历、层序遍历，下面就一一简单地实现出二分搜索树中的这几种遍历方式。前序遍历
对于二分搜索树的前序遍历操作，同样也是使用递归来实现。对于前序遍历，遍历的顺序是先访问当前节点，接着访问该节点的左子树继而访问该节点的右子树，在子树中也是重复此步骤。当遍历到一个节点为null时直接返回即可。用图来表示这个过程就是以下所示:
以上过程实现为代码形式如下:
实现了代码之后，做个小测试验证一下是否正确，测试代码如下:
测试结果如下，可以看出结果是符合前序遍历的规则的，验证了代码的正确性:
在实现了前序遍历之后，可以使用前序遍历的方式为这个BST类重写一下toString方法打印出二分搜索树以便观察。实现代码如下:
同样也对此测试一下:
运行效果如下，可以看出同一层的节点都打印了正确的深度，遍历的顺序也满足了前序遍历的规则:
至此，就完成了前序遍历的实现，对于下面的中序遍历和后序遍历本质上实现方式和前序遍历差不了多少，只是节点的访问顺序变化了。中序遍历
对于中序遍历，遍历的顺序是先访问当前节点的左子树，接着访问该节点继而访问该节点的右子树，在子树中也是重复此步骤。当遍历到一个节点为null时直接返回即可。用图来表示这个过程就是以下所示:
以上过程实现为代码形式如下:
同样对此也调用该方法测试一下，运行结果如下，可以看出输出的顺序符合中序遍历的规则，验证了代码的正确性:
从结果中也可以看出中序遍历的一个特点：输出的结果是排好序后的。原因在于二分搜索树的左子树是小于父亲节点，右子树大于父亲节点，而中序遍历的顺序正好是先访问左子树，接着访问父亲节点，最后再访问右子树。所以输出的结果是按从小到大的顺序输出的。后序遍历
对于后序遍历，遍历的顺序是先访问当前节点的左子树，接着访问该节点的右子树继而访问该节点，在子树中也是重复此步骤。当遍历到一个节点为null时直接返回即可。用图来表示这个过程就是以下所示:
以上过程实现为代码形式如下:
同样对此也调用该方法测试一下，运行结果如下，可以看出输出的顺序符合中序遍历的规则，验证了代码的正确性:
从结果中也可以看出后序遍历是按从后往前的顺序由子节点开始一一遍历到父节点的，这种特性也应对了一种应用：为二分搜索树释放内存。当想要为一个符合二分搜索树特性的模型释放内存的时候，就可以使用二分搜索树的后序遍历来完成。前、中、后序遍历的非递归实现
在实现了前、中、后序遍历的递归方式之后，可以使用非递归方式对这三种遍历一一再实现一次，加深对二分搜索树的理解。在对递归的学习中，可以知道递归调用函数的时候是会被压入到系统栈中记录执行顺序的，当执行完之后就进行出栈回到上一次调用函数的地方继续执行余下操作。所以对于非递归的实现，可以借助栈这个数据结构，手动模拟系统栈的方式实现二分搜索树的前、中、后序遍历。接下来一一实现这三种遍历的非递归方式。前序遍历的非递归实现
对于使用栈来帮助模拟系统栈来实现前序遍历的过程，用动图来表示如下所示：
对于以上过程，由于栈的后进先出的特性，加上前序遍历的规则，所以在遍历完一个节点将其出栈后是先将该节点的右节点先入栈再入栈左节点，这样子后续出栈遍历节点后就满足了前序遍历的规则。以上过程代码实现如下:
实现之后，调用之前的递归方式和这个非递归方式比对两者的结果是否一致:
从结果可看出，非递归方式的实现是正确的。对比递归实现的步骤，非递归的实现相对来说还是比较复杂的，不过通过这样的实现也能加强对于二分搜索树前序遍历的理解，还是相当有好处的，接着继续实现中序遍历和后序遍历的非递归方式的实现。中序遍历的非递归实现
对于中序遍历的非递归实现，同样也是使用一个栈来模拟系统栈的递归过程来实现，首先在这里先使用一个内部类用于封装当前的指令（继续模拟递归、打印节点）和当前模拟递归到的节点，以便模拟栈递归实现中序遍历。对于这个内部类的具体实现如下所示，其中s代表指令，如果s为go则表示继续模拟递归，如果s为print则表示打印当前节点信息。
当封装了这么一个内部类之后，非递归方式的中序遍历就比较好实现了，具体过程为:首先先从栈顶取出当前栈顶信息。接着判断栈顶信息中的指令是否为print，如果为print打印节点信息，否则做下面的操作。如果指令为go，则将当前节点的右子树和指令go先入栈。（和前面的非递归前序遍历一样，由于栈的后入先出特性，需要反过来入栈，后面出栈时才能符合中序遍历）接着将当前节点和指令print入栈，当后面这个节点出栈时就可以判断到print指令打印这个节点。最后再将当前节点的左子树和指令go入栈，这样子后面最先出栈的就是左节点再到左节点的父节点再到右节点，满足中序遍历的规则。初始时将根节点和指令go入栈，表示从根节点开始继续模拟递归下去。接着开始循环，只要栈不为空，就重复循环中的内容:这样子，重复以上过程，就可以模拟系统栈的递归实现出二分搜索树的中序遍历了，以上过程的图示演示如下:
具体代码实现如下:
同样地，也对此进行测试，验证是否编写正确，运行结果如下:
从测试结果可以看出，遍历的结果是符合预期的，和之前实现的递归方式的结果是一致的，验证了代码的正确性。在实现完了非递归方式的中序遍历后，对于后序遍历也就手到擒来了，原理也是相似的，接下来就实现后序遍历的非递归方式。后序遍历的非递归实现
对于后序遍历的非递归方式的实现，同样也是使用Command来封装入栈的信息。其中的具体实现过程如下:首先先从栈顶取出当前栈顶信息。接着判断栈顶信息中的指令是否为print，如果为print打印节点信息，否则做下面的操作。如果指令为go，则将当前节点和指令print先入栈，当后面这个节点出栈时就可以判断到print指令打印这个节点。（和前面的非递归前序遍历一样，由于栈的后入先出特性，需要反过来入栈，后面出栈时才能符合后序遍历）接着将当前节点的右子树和指令go入栈。最后再将当前节点的左子树和指令go入栈，这样子后面最先出栈的就是左节点再到右节点再到左右节点的父节点，满足后序遍历的规则。初始时将根节点和指令go入栈，表示从根节点开始继续模拟递归下去。接着开始循环，只要栈不为空，就重复循环中的内容:这样子，重复以上过程，就可以模拟系统栈的递归实现出二分搜索树的后序遍历了，以上过程的图示演示如下:
具体代码实现如下:
同样地，也对此进行测试，验证是否编写正确，运行结果如下:
从测试结果可以看出，遍历的结果是符合预期的，和之前实现的递归方式的结果是一致的，验证了代码的正确性。至此，就将前、中、后序遍历的非递归方式都实现了一遍了，使用的是模拟系统栈的方式，如此也加深了对这三种遍历的理解以及对递归的理解，接下来就实现二分搜索树中的最后一种遍历层序遍历。层序遍历
在前面的前、中、后序三种遍历方式的实现过程中，可以发现这三种遍历方式总是会先到最下层的节点处再往上返回，这种方式也就是深度优先遍历。而对于层序遍历而言，它是按一层一层从左往右的顺序来遍历的，这种方式也就是广度优先遍历。对于这种遍历方式，通常使用的实现方式是非递归方式的实现，同时可以借助队列这个数据结构来实现。对于实现过程，当一个节点入队并出队时，这个节点就被遍历到了，同时在该节点出队时，由于队列的先入先出特性以及层序遍历的规则，此时将该节点的左右节点按左节点、右节点的顺序入队，此时再当队首的节点出队时，又再将出队节点的左右节点按左节点、右节点的顺序入队。以此类推循环往复，就完成了二分搜索树的层序遍历操作，这个过程用图来表示如下所示:
以上过程代码实现如下:
此时调用该方法验证是否正确:
从结果可看出，遍历的顺序符合了预期，验证了代码的正确性。至此，二分搜索树的几种遍历方式也就都实现了，接下来实现最后的删除操作。删除操作
删除最大元素和最小元素
对于删除操作，首先先从删除二分搜索树的最大值和最小值开始，因为根据二分搜索树的特性，最左边的节点就是整棵树的最小值，最右边的节点就是整棵树的最大值，所以相对来说这两个操作比较容易实现，同时先实现了这两个操作后，对于后续的删除任意元素也有辅助的作用。以下是最大值和最小值的几个示例图:
在实现删除的操作之前，先实现两个函数用于找到二分搜索树的最小元素和最大元素以备删除时使用，具体实现如下:
在实现完以上函数之后，就可以进行删除的操作了。首先先进行最小值的删除，对于最小值的删除，有两种情况：删除的节点是叶子节点、删除的节点有右子树。对于叶子节点，直接删除即可。而对于有右子树的节点，删除的逻辑也很简单，即将当前的节点和树脱离，再将这个节点的右子树接到它原来的位置即可。而对于叶子节点，它的左右节点都是null的，所以对于叶子节点也可以使用这个逻辑来删除，只不过接到节点原来位置的是null而已。以上过程的图示如下:
代码实现如下:
在处理完了最小元素的删除之后，对于最大的元素删除就容易许多了，删除的逻辑总体上还是一样的，也就是把删除节点的左子树接到节点原来的位置即可。删除过程图示如下:
代码实现如下:
在实现了以上两个操作之后，对它们进行一下测试。测试的逻辑为：随机生成个[0,0)的数添加到二分搜索树中，然后分别使用这两个操作将删除的元素添加到一个ArrayList中，再对这个ArrayList进行校验，看看里面的元素是不是按从小到大的顺序或从大到小的顺序排列，校验成功的话说明以上的操作实现的代码是正确的。测试代码如下所示:
运行结果
从运行结果中，可以看出以上实现的两个删除操作都是正确的，接下来就可以实现任意元素的删除了。删除任意元素
对于删除二分搜索树中的任意元素，同样也分为几种情况：删除只有左孩子的节点、删除只有右孩子的节点、删除左右都有孩子的节点。对于前面两种情况：删除只有左孩子的节点、删除只有右孩子的节点，具体步骤其实和前面的删除最大节点和删除最小节点差不多，也是将删除的节点的左子树或者右子树挂接在这个节点原来的位置，将原来的节点从二分搜索树中脱离出去，所以对于这两种情况的删除，实现起来和前面的基本相同。而对于删除左右都有孩子的节点这种情况，就不能使用前面的法子了，这个时候可以使用Hibbard提出的HibbardDeketion原理进行删除。具体步骤是这样的：先将要删除的节点记录为d，然后从d的右子树中找到子树中最小的节点用s记录下来，这个s也就是d的后继节点。然后将d的右子树中删除掉最小的节点，也就是s，并将删除s后的这个右子树的根赋值给s的右节点。也就是s从右子树中最小的位置移到了根的位置。接着再将d的左子树赋值给s的左子树。最后将d从二分搜索树中脱离出来，将s接到d的位置。此时，d就从树中删除掉了。以上步骤简单来说就是d的右子树的节点都是大于d的，而其中的最小节点就是排在它后面的节点，此时如果将这个s放到d的位置，这个s节点的左子树依然满足都小于它的特性、同样右子树也满足都大于它的特性，此时就可以达到删除d的效果了。同理，也可以在d的左子树中找它的前驱，也就是左子树中最大的节点，用p记录下来，再将这个p按照以上操作s的原理将p放置到d的位置，也可以达成删除d的效果。这里就不实现这个找前驱的操作了，实现找后继s的操作来删除d。对于以上删除的步骤，表示为图为以下所示:删除只有左孩子的节点示例:
删除只有右孩子的节点示例:
删除左右孩子均有的节点示例:
代码实现如下:
实现完之后，也对此测试一下，以验证代码的正确性，测试代码如下:
运行结果
零基础编程从入门到精通全套7册PythonHTML+CSSJavaLinuxJavaScriptiOS基础核心进阶实战编程书淘宝旗舰店￥￥购买已下架