大家好，我是多选参数的程序锅，一个正在”研究“操作系统、学数据结构和算法以及Java的疯狂猛补生。本篇将带来的是二叉查找树的相关知识，知识提纲如图所示。
另外由于极客时间的《数据结构也算法之美》专栏的图太好看了，所以本篇很多地方直接使用了专栏的图片。
1.基本介绍二叉查找树又名二叉搜索树又或者叫做二叉排序树，是二叉树中最常用的一种类型。二叉查找树是为了实现快速查找而生的。除了支持动态数据集合的快速查找之外，还支持动态数据集合的快速插入或删除一个数据。
之所以可以快速插入、删除、查找一个数据，是因为二叉查找树的特殊结构。二叉查找树要求树中的任何一个节点，其左子树的每个节点的值都要小于这个节点的值，而右子树的每个节点的值都大于这个节点的值。如图所示。
2.查找操作先取根节点，如果根节点就等于我们要查找的数据，那就返回。如果要查找的数据比根节点要小，那么就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。
实现的代码如下所示：
publicNodefindNode(intdata){Nodep=this.tree;while(p!=null){if(p.data==data){returnp;}elseif(p.datadata){p=p.right;}else{p=p.left;}}returnnull;}3.插入操作
类似于查找操作，我们只需要从根节点开始，依次比较要插入的数据和节点的大小关系。这里先考虑插入数据跟已有数据不重复。如果插入的数据比节点的数据大，并且节点的右子树为空，那么直接插到右子节点的位置；如果不为空，则再递归遍历右子树，查找插入的位置。同理，如果要插入的数据比节点的数值小也是类似的。
实现的代码如下所示：
publicvoidaddNode(intdata){if(this.tree==null){this.tree=newNode(data);return;}Nodep=this.tree;while(p!=null){if(p.datadata){if(p.right==null){p.right=newNode(data);return;}p=p.right;}else{if(p.left==null){p.left=newNode(data);return;}p=p.left;}}}4.删除操作
相比查找和插入操作，删除操作要繁琐的多。下面分三种情况进行讨论，当然最一开始的是先找到要删除的节点：
如果要删除的节点没有子节点，我们只需要将父节点指向要删除节点的指针置为null。比如图中的节点55。
如果要删除的节点只有一个子节点（左或者右），我们就可以将它的子节点更新为父节点。比如图中的节点13。
如果要删除的节点有两个子节点。那么需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点位置上。此时，还需要删掉最小节点在原来的位置，可以使用前两条规则来删除这个最小节点（因为最小节点不存在左子节点，即只存在右子节点或者也不存在右子节点）。比如图中的节点18。
★当然这边也可以找到左子树中的最大节点。
”实现的代码如下所示，该段代码采用了一丢丢所谓的技巧，技巧的阐述可看注释。
publicvoiddeleteNode(intdata){Nodep=this.tree;NodepParent=null;//p的父节点while(p!=nullp.data!=data){pParent=p;if(p.datadata){p=p.right;}else{p=p.left;}}if(p==null){return;}//要删除的节点有左右子节点if(p.left!=nullp.right!=null){NodeminP=p.right;NodeminPP=p;//minP的父节点while(minP.left!=null){minPP=minP;minP=minP.left;}p.data=minP.data;//将minP的数据替换到p中/*技巧：对右子树中最小的节点进行删除，这种情况跟要删除的节点只有一颗子树或者没有子树情况一样，所以这边将minPP赋值给pParent，minP赋值给p，那么重复使用一段代码*/pParent=minPP;p=minP;}Nodechild=null;//要删除的节点只有左节点的情况if(p.left!=null){child=p.left;}elseif(p.right!=null){//要删除的节点只有右子节点的情况child=p.right;}else{//要删除的节点左右子节点都无的情况child=null;}//删除的是根节点的情况if(pParent==null){this.tree=child;}//将p父节点的左/右子树重新指向if(pParent.left==p){pParent.left=child;}elseif(pParent.right==p){pParent.right=child;}}★
对于二叉树的删除操作，还有一种方式就是将节点标记为“已删除”，但是又不真正地删除节点。这样会比较浪费内存空间，但是删除操作变得简单多了。并且也没有增加查找、添加操作的难度，只需要额外判断该节点是否标记为已删除。
”5.其他操作二叉查找树还可以支持快速查找最大节点、最小节点。除此之外，要想通过二叉查找树得到有序数据序列，只需要中序遍历二叉查找树，时间复杂度为O(n)。所以，二叉查找树也叫二叉排序树。
publicNodefindMin(){Nodep=this.tree;while(p!=nullp.left!=null){p=p.left;}//这个情况相当于树为空的情况if(p==null){returnnull;}returnp;}publicNodefindMax(){Nodep=this.tree;while(p!=nullp.right!=null){p=p.right;}if(p==null){returnnull;}returnp;}★
前驱结点和后继节点（二叉树前驱节点和后继节点：一个二叉树中序遍历中某个节点的前一个节点叫该节点的前驱节点，某个节点的后一个节点叫后继节点）。这个操作针对一般的二叉树也有，而且一般的二叉树和二叉查找树在解决这个问题上好像并无区别。但是二叉查找树可以利用中序遍历的方式，将遍历的结果以及节点的位置保存到数组中。之后通过索引值+1，-1的方式即可访问到前驱节点和后继节点。一般方式可参考：