前言在树与二叉树中，已经介绍过了关于树的一些基本概念以及二叉树的前中后序遍历，而这篇文章将是在二叉树的基础上来展开讲解的二叉搜索树，也就是说二叉搜索树建立在树的基础之上。至于博主为何要花一整篇文章来讲这个二叉搜索树呢？原因很简单，红-黑树是基于二叉搜索树的，如果对二叉搜索树不了解，那还谈何红-黑树？红-黑树的重要性我想各位没吃过佩奇肉也肯定看过宜春跑....是的，jdk1.8的Map就是散列表+红黑树实现的！
[toc]首先要明确的是二叉搜索树又称二叉排序树、二叉查找树，简统称BST
1、二分法引言在正式将二叉搜索树之前，宜春还是想先谈谈人生谈谈生活从而切入二叉搜索树。
一天，程序员老方给宜春打靓仔，我今天下单了一双皮鞋，老靓了，价格不菲啊！宜春：得了吧你，啥条件啊我还不知道，还皮鞋，老鼠皮的鞋吧，如果是真牛皮的皮鞋我把它吃喽！！！老方：你还真别说，这皮鞋还真是比真牛皮还真的假牛皮的皮鞋，老靓了，你猜猜我买它花了多少银子，反正是以内，看你能不能再最少次数猜出来，要是五次机会之内猜出来就亲自下厨，炖给你吃，嘎嘣脆，嘿嘿...宜春：你就嘚瑟吧，还是你懂我，知道我好这一口（自黑）....咳咳咳，50块老方：不对，价格高了宜春：25老方：不对，价格还高了宜春：12.5....
一个一个字看这里的估计在座各位个个都是人才，就一个简简单单的二分法猜数字的游戏，通过对猜测数字“大了”、“小了”的情况判断，来猜出最终的数字。当然，本改三言两语就可以描述的，宜春花了这么长串字符串来描述，估计宜春TM也是个人才....实际上呢，宜春就想活跃活跃下气氛，把各位的脑细胞集中一下下，当然耽误了各位时间，属实抱歉，宜春在线挨揍....
不知各位有没有想过，为何二分法就是有足够的优势呢？如果以内我直接猜25不行么？这样岂不是更可能定出价格？其实直接猜25或者更小这是一种极端的猜测，如果确实比25小，那范围就是在25以内了，那你有没有想过:如果大于25呢？范围就直接转成了75了！随着这种极端思想的推进，会发现每次择半查找会更加准确和更好的能应对各种不确定的情景！择半查找复杂度为O(log_2n)，即最多需要O(log_2n)次可以猜到最终数字。
到这里，要开始正式介绍二叉搜索树了，实际上二叉搜索树就类似于上面提到过的二分查找，有类似的韵味。
2、二叉搜索树定义二叉查找树（BinarySearchTree，BST）是一种特殊的二叉树，一棵二叉搜索树（BST）是一棵二叉树，其中，对于树中每个节点而言：1、若其左子树存在，则其左子树中每个节点的值都不大于该节点值；2、若其右子树存在，则其右子树中每个节点的值都不小于该节点值。
在这里插入图片描述3、二叉搜索树的CRUD我想提一下的是：我们知道遍历树是使用前中后序遍历方法，但是遍历二叉搜索树最好是使用中序遍历法，如果不理解为何使用中序遍历，那么你有三种选择：一、自行树与二叉树进去补补基础树基础二、留言提问，宜春看到就回三、前面二者都拒绝，那你就优秀了....
3.1、查找如果要在二叉查找树中查找任意一个节点，假设它是X，我们可以分为以下几步：
1、如果二叉查找树为空，则返回空操作，否则，执行一下操作；2、先取根节点，如果节点X等于根节点，则返回；3、如果节点小于根节点，则递归查找左子树；4、如果节点大于根节点，则递归查找右子树。
在这里插入图片描述//查找的逻辑代码实现：/***
paramvalue希望查找结点的值*return如果找到返回该结点，否则返回null*/publicNodesearch(intvalue){if(value==this.value){//找到就是该结点returnthis;}elseif(valuethis.value){//如果查找的值小于当前结点，向左子树递归查找//如果左子结点为空if(this.left==null){returnnull;}returnthis.left.search(value);}else{//如果查找的值不小于当前结点，向右子树递归查找if(this.right==null){returnnull;}returnthis.right.search(value);}}3.2、插入在二叉树中插入一个节点，仔细想想，会发现插入某一个节点一般都是插入到叶节点上，所以只需从根结点开始，依次遍历比较要插入的数据和节点的大小关系。
==二叉查找树有一个很重要的特性就是插入的实现难度和查找差不多==。插入节点其实可以有如下三种情况：
1、如果树是空的，则直接将新节点插入，否则，执行下面步骤。2、要插入的数据比根节点数据大，则到右子树中插入新数据，如果右子树为空，则将新数据直接插入到右子节点的位置；不为空，则继续遍历右子树，查找插入位置。3、要插入的数据比根节点数据小，则到左子树中插入数据，如果左子树为空，则直接将新数据插入到左子节点的位置；不为空，则继续遍历左子树，查找插入的位置。
在这里插入图片描述//添加结点的逻辑代码//递归的形式添加结点，注意需要满足二叉排序树的要求publicvoidadd(Nodenode){if(node==null){return;}if(root==null){root=node;//如果root为空则直接让root指向node}//判断传入的结点的值，和当前子树的根结点的值关系if(node.valuethis.value){//如果当前结点左子结点为nullif(this.left==null){this.left=node;}else{//递归的向左子树添加this.left.add(node);}}else{//添加的结点的值大于当前结点的值if(this.right==null){this.right=node;}else{//递归的向右子树添加this.right.add(node);}}}3.3、删除
可以这么说，删除相对查找和插入来说比较复杂一些，为啥会复杂一些呢？因为要删除某一个节点，首先要查找到这个节点然后将其删除，删除之后还需要将该二叉搜索树还原成一颗二叉搜索树。因此针对要删除节点的子节点位置的不同，同样一般分为三种情况来处理：
1、第一种情况，如果要删除的节点没有子节点，直接将父节点指向要删除节点的指针指向null。比如途中要删除的节点0。2、第二种情况，如果要删除的节点只有一个节点，即只有左子节点或右子节点，则将父节点指向要删除节点的指针指向要删除节点的子节点即可。比如途中要删除的节点1。3、第三种情况，如果要删除的节点有两个子节点，则需要先找到这个节点右子树中的最小节点或者左子树中的最大节点，将其替换到要删除的节点上。然后删除这个右子树中的最小节点或左子树中的最大节点，比如图中要删除的节点6。
在这里插入图片描述//删除结点逻辑代码publicvoiddelNode(intvalue){if(root==null){return;}else{//1.需求先去找到要删除的结点targetNodeNodetargetNode=search(value);//如果没有找到要删除的结点if(targetNode==null){return;}//如果我们发现当前这颗二叉排序树只有一个结点if(root.left==nullroot.right==null){root=null;return;}//去找到targetNode的父结点Nodeparent=searchParent(value);//如果要删除的结点是叶子结点if(targetNode.left==nulltargetNode.right==null){//判断targetNode是父结点的左子结点，还是右子结点if(parent.left!=nullparent.left.value==value){//是左子结点parent.left=null;}elseif(parent.right!=nullparent.right.value==value){//是由子结点parent.right=null;}}elseif(targetNode.left!=nulltargetNode.right!=null){//删除有两颗子树的节点intminVal=delRightTreeMin(targetNode.right);targetNode.value=minVal;}else{//删除只有一颗子树的结点//如果要删除的结点有左子结点if(targetNode.left!=null){if(parent!=null){//如果targetNode是parent的左子结点if(parent.left.value==value){parent.left=targetNode.left;}else{//targetNode是parent的右子结点parent.right=targetNode.left;}}else{root=targetNode.left;}}else{//如果要删除的结点有右子结点if(parent!=null){//如果targetNode是parent的左子结点if(parent.left.value==value){parent.left=targetNode.right;}else{//如果targetNode是parent的右子结点parent.right=targetNode.right;}}else{root=targetNode.right;}}}}}3.4、整体代码
为了连贯一下思维，可以自行编辑main方法进行测试！
packagedataStructure;//创建二叉排序树classBinarySortTree{privateNoderoot;publicNodegetRoot(){returnroot;}//查找要删除的结点publicNodesearch(intvalue){if(root==null){returnnull;}else{returnroot.search(value);}}//查找父结点publicNodesearchParent(intvalue){if(root==null){returnnull;}else{returnroot.searchParent(value);}}//编写方法://1.返回的以node为根结点的二叉排序树的最小结点的值//2.删除node为根结点的二叉排序树的最小结点/****
paramnode传入的结点(当做二叉排序树的根结点)*return返回的以node为根结点的二叉排序树的最小结点的值*/publicintdelRightTreeMin(Nodenode){Nodetarget=node;//循环的查找左子节点，就会找到最小值while(target.left!=null){target=target.left;}//这时target就指向了最小结点//删除最小结点delNode(target.value);returntarget.value;}//删除结点publicvoiddelNode(intvalue){if(root==null){return;}else{//1.需求先去找到要删除的结点targetNodeNodetargetNode=search(value);//如果没有找到要删除的结点if(targetNode==null){return;}//如果我们发现当前这颗二叉排序树只有一个结点if(root.left==nullroot.right==null){root=null;return;}//去找到targetNode的父结点Nodeparent=searchParent(value);//如果要删除的结点是叶子结点if(targetNode.left==nulltargetNode.right==null){//判断targetNode是父结点的左子结点，还是右子结点if(parent.left!=nullparent.left.value==value){//是左子结点parent.left=null;}elseif(parent.right!=nullparent.right.value==value){//是由子结点parent.right=null;}}elseif(targetNode.left!=nulltargetNode.right!=null){//删除有两颗子树的节点intminVal=delRightTreeMin(targetNode.right);targetNode.value=minVal;}else{//删除只有一颗子树的结点//如果要删除的结点有左子结点if(targetNode.left!=null){if(parent!=null){//如果targetNode是parent的左子结点if(parent.left.value==value){parent.left=targetNode.left;}else{//targetNode是parent的右子结点parent.right=targetNode.left;}}else{root=targetNode.left;}}else{//如果要删除的结点有右子结点if(parent!=null){//如果targetNode是parent的左子结点if(parent.left.value==value){parent.left=targetNode.right;}else{//如果targetNode是parent的右子结点parent.right=targetNode.right;}}else{root=targetNode.right;}}}}}//添加结点的方法publicvoidadd(Nodenode){if(root==null){root=node;//如果root为空则直接让root指向node}else{root.add(node);}}//中序遍历publicvoidinfixOrder(){if(root!=null){root.infixOrder();}else{System.out.println("二叉排序树为空，不能遍历");}}}//创建Node结点classNode{intvalue;Nodeleft;Noderight;publicNode(intvalue){this.value=value;}//查找要删除的结点/****paramvalue希望删除的结点的值*return如果找到返回该结点，否则返回null*/publicNodesearch(intvalue){if(value==this.value){//找到就是该结点returnthis;}elseif(valuethis.value){//如果查找的值小于当前结点，向左子树递归查找//如果左子结点为空if(this.left==null){returnnull;}returnthis.left.search(value);}else{//如果查找的值不小于当前结点，向右子树递归查找if(this.right==null){returnnull;}returnthis.right.search(value);}}//查找要删除结点的父结点/****paramvalue要找到的结点的值*return返回的是要删除的结点的父结点，如果没有就返回null*/publicNodesearchParent(intvalue){//如果当前结点就是要删除的结点的父结点，就返回if((this.left!=nullthis.left.value==value)(this.right!=nullthis.right.value==value)){returnthis;}else{//如果查找的值小于当前结点的值,并且当前结点的左子结点不为空if(valuethis.valuethis.left!=null){returnthis.left.searchParent(value);//向左子树递归查找}elseif(value=this.valuethis.right!=null){returnthis.right.searchParent(value);//向右子树递归查找}else{returnnull;//没有找到父结点}}}
OverridepublicStringtoString(){return"Node[value="+value+"]";}//添加结点的方法//递归的形式添加结点，注意需要满足二叉排序树的要求publicvoidadd(Nodenode){if(node==null){return;}//判断传入的结点的值，和当前子树的根结点的值关系if(node.valuethis.value){//如果当前结点左子结点为nullif(this.left==null){this.left=node;}else{//递归的向左子树添加this.left.add(node);}}else{//添加的结点的值大于当前结点的值if(this.right==null){this.right=node;}else{//递归的向右子树添加this.right.add(node);}}}//中序遍历publicvoidinfixOrder(){if(this.left!=null){this.left.infixOrder();}System.out.println(this);if(this.right!=null){this.right.infixOrder();}}}publicclassBinarySortTreeDemo{//==========至于main方法的测试代码可自行调整测试！！！！！！！！！publicstaticvoidmain(String[]args){int[]arr={4,7,2,13,11,5,1,9,3};BinarySortTreebinarySortTree=newBinarySortTree();for(inti=0;iarr.length;i++){binarySortTree.add(newNode(arr[i]));}binarySortTree.add(newNode(4));System.out.println("中序遍历二叉排序树~");binarySortTree.infixOrder();}}4、二叉搜索树的两种极端情况1、变成一颗完全二叉树，所有节点尽量填满树的每一层，上一层填满后还有剩余节点的话，则由左向右尽量填满下一层。如下图所示，即为一颗完全二叉树；2、每一层只有一个节点的二叉树。如下图所示：我敲，这不是蛇皮怪单链表吗，是的，给我们的感觉就是树形怪退化为蛇皮怪单链表了！在这种情况下，树中每层只有一个节点，该状态的树结构更倾向于一种线性结构，节点的查询类似于数组的遍历，复杂度为O(n)。
也正是因此，后面就出现了平衡二叉树，就涉及到了左旋右旋花里胡哨的蛇皮操作，当然这只是提一下，并不在本文的范畴之内，不过后续应该会写这方面的文章，尽量吧.....
5、二叉搜索树总结二叉搜索树又称二叉排序树、二叉查找树，简统称BST
根据二叉搜索树的特性，==可知比较次数等于给定值节点在二叉排序树中的层数==。遍历的话使用中序遍历。如果二叉排序树是平衡的，则n个节点的二叉排序树的高度为Log2n+1,其查找效率为O(Log2n)，近似于折半查找。如果二叉排序树完全不平衡，则其深度可达到n，查找效率为O(n)，退化为顺序查找。一般的，二叉排序树的查找性能在O(Log2n)到O(n)之间。因此，为了获得较好的查找性能，就要构造一棵平衡的二叉排序树。而平衡二叉树可能又要涉及到了左旋右旋花里胡哨的蛇皮操作，当然这只是提一下，并不在本文的范畴之内，不过后续应该会写这方面的文章，尽量吧.....
如果本文对你有一点点帮助，那么请点个赞呗，谢谢~
最后，若有不足或者不正之处，欢迎指正批评，感激不尽！如果有疑问欢迎留言，绝对第一时间回复！