二叉搜索树

✨前言✨

 博客主页：to Keep博客主页
欢迎关注，点赞，留言评论
⏳首发时间：2022年3月6日
 博主码云地址：博主码云地址
参考书籍：java核心技术 卷1
编程练习：牛客网+力扣网
由于博主目前也是处于一个学习的状态，如有讲的不对的地方，请一定联系我予以改正！！！

1 二叉搜索树的概念2 二叉搜索树的查找3 二叉搜索树的插入4 二叉搜索树的删除（重点）

4.1 cur.left==null时4.2 cur.right==null时4.3 cur.left!=null&&cur.right!=null时 5 总结：

二叉搜索树是可以特殊的二叉树，也叫二叉排序树

特点：
1 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
3 它的左右子树也分别为二叉搜索树
4 中序遍历是有序的

思路：主要就是依据二叉搜索树的特点，右边的数值会更大，左边的会更小

    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;
    }

    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;
    }

当cur.left==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;
                    }
                }
        }
    }

对于二叉搜索树而言最核心的部门还是依据右树会比左树大，左树比右树大的特点，最为核心的部门其实还是对于二叉搜索树的删除操作，比较难理解，情况众多，其实见多了也自然就会了！！