1 二叉搜索树的概念
二叉搜索树是可以特殊的二叉树，也叫二叉排序树
特点：
1 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
3 它的左右子树也分别为二叉搜索树
4 中序遍历是有序的
2 二叉搜索树的查找
思路：主要就是依据二叉搜索树的特点，右边的数值会更大，左边的会更小
public boolean find(int val){ //根节点为空，说明是一棵空树 if (root==null)return false; Node cur = root; while (cur!=null){ if(val>cur.val){//说明在数的右边 cur=cur.right; }else if(val== cur.val){//找到了 return true; }else{//说明在树的左边 cur=cur.left; } } //说明没有找到 return false; }
3 二叉搜索树的插入
public boolean insert(int val){ if (root==null){ //头结点为空，则刚插入进来的节点就是根节点 root = new Node(val); return true; } Node cur = root; Node parent = null;//用来记录cur上一个位置 while (cur!=null){ if (val>cur.val){ parent=cur; cur=cur.right; }else if(cur.val==val){ return false; }else{ parent=cur; cur=cur.left; } } Node node = new Node(val); if (val>parent.val){ parent.right=node; }else{ parent.left=node; } return true; }
4 二叉搜索树的删除（重点）
4.1 cur.left==null时
当cur.left==null时则有一下情况
4.2 cur.right==null时
4.3 cur.left!=null&&cur.right!=null时
思路：我们采用替换法，就是利用parent和cur的方法，先找到cur所在的位置，在定义一个变量tmp指向cur，另一个tag变量等于cur.right，然后从cur的右树中去寻找到最小值，然后tag找到最小值的位置后，在让cur的值等于这个最小值，接下来就变成了删除tag了，删除tag有以下两种情况：
结合以上的所有情况，所以代码如下：
public void remove(int val){ if(root==null)return; Node cur = root; Node parent = null; //找要删除的值 while (cur!=null){ if (val>cur.val){ parent=cur; cur=cur.right; }else if(val== cur.val){ toremove(cur,parent); break; }else{ parent=cur; cur=cur.left; } } } public void toremove(Node cur,Node parent){ if(cur.left==null){ if(cur.left==null){ if(cur==root){ root=root.right; } if(parent.left==cur){ parent.left=cur.right; } if (parent.right==cur){ parent.right=cur.right; } }else if(cur.right==null){ if(cur==root){ root=root.right; } if(parent.right==cur){ parent.right=cur.left; } if(parent.left==cur){ parent.left=cur.left; }else{ Node tmp = cur; Node tag = cur.right; while (tag.left!=null){ tmp=tag; tag=tag.left; } //交换 cur.val= tag.val; //删除tag if (tmp.right==tag){ tmp.right=tag.right; }else{ tmp.left=tag.right; } } } }
5 总结：
对于二叉搜索树而言最核心的部门还是依据右树会比左树大，左树比右树大的特点，最为核心的部门其实还是对于二叉搜索树的删除操作，比较难理解，情况众多，其实见多了也自然就会了！！
