        //如果cur的val值小于key说明key在cur的右边
        if (cur.val<key)
        {
            //cur等于cur的右子树
           cur=cur.right;
        }
        //如果cur的val值比key大,说明key在cur的左边
        else if (cur.val>key)
        {
            //cur等于cur的左子树
            cur=cur.left;
        }
        //如果cur的val值等于key,说明找到了,则返回true
        else {
            return true;
        }
    }
    //如果cur为空还没有找到key说明key在搜索二叉树中不存在返回false
    return false;
}

二叉搜索树插入操作

插入操作思路

1.如果根结点为空,直接让插入元素val插入到根结点位置

2.如果根结点不为空

如果val大于根结点则继续判断root右子树和val大小关系

如果val小于根结点则继续判断root左子树和val大小关系

3.如下图所示,当我们走到结点值为9的位置发现val=10仍然大于9

然后继续往9的右子树走,发现为空

我们将val=10插入9的右子树,但是我们没有记录9这个结点,无法向9这个结点的右子树插入val

所以我们需要记录最近一次到达的上一个结点,以便可以将结点连接在一起

4.如果val是二叉搜索树中的结点值其中之一

比如val=5,这无法插入

因为二叉搜索树中的元素一定是没有重复的

要么比任意结点小,要么比任意结点大

不可能出现两个结点相同的情况

所以当出现插入元素和二叉搜索树中元素相同时,我们选择返回false

插入代码详解

public boolean insert(int val)
{
    //如果根结点为空则将插入结点作为根结点
    if (root==null)
    {
        root=new TreeNode(val);
        return true;
    }
    //如果根结点不为空,将root赋值给cur
    TreeNode cur=root;
    //创建prent记录cur到达的上一个结点
    TreeNode parent=null;
    //当cur不为空
    while (cur!=null) {
        //如果cur的val值比插入值小,则让parent记录当前cur结点,并且cur等于cur的右子树
        if (cur.val < val) {
            parent=cur;
            cur = cur.right;
        }
        //如果cur的val值比插入值大,则让parent记录当前cur结点,并且cur等于cur的左子树
        else if (cur.val > val) {
            parent=cur;
            cur = cur.left;
        }
        //如果cur的val值等于插入值,则无法插入,返回false
        else {
            return false;
        }
    }
    //当cur==null说明cur已经到达了要插入的位置
    TreeNode node=new TreeNode(val);
    //如果插入值比cur到达的上一个结点值大,则插入在上一个结点值的右边
    if (val> parent.val)
    {
        parent.right=node;
    }
    //如果插入值比cur到达的上一个结点值小,则插入在上一个结点值的左边
    else {
        parent.left=node;
    }
    //最后插入完成返回true
    return true;
}

接下来讲解一下搜索二叉树删除操作(有点难)

大家跟紧我的思维!

二叉搜索树删除操作

删除操作思路

首先咱们思考一下,删除搜索二叉树结点元素我们需要考虑什么问题

1.首先要遍历搜索二叉树找到要删除的结点

2.考虑搜索二叉树为空,没有结点的情况,无法删除

3.考虑搜索二叉树删除结点的左子树为空的情况如下图,cur为要删除结点

4.考虑搜索二叉树删除结点的右子树为空的情况,这里就不展示了,和上面情况差不多

5.考虑搜索二叉树删除结点的左子树右子树都不为空的情况(认真理解)

这里统一采用找到删除结点的右子树最深左结点的方法

找到get分两种情况下图是第一种

下图是第二种

以上内容我最开始也想不出来,但是做多了关于二叉树的题之后,也渐渐找到了这类型题的规律

基本上任何二叉树的题都和遍历二叉树有关系,也就是在遍历二叉树的基础上

无非是比较结点大小,或者结点是否存在等等变化,大家可以试着体会一下

删除代码详解

这里用了两个方法

1.第一个方法是找到要删除的结点

2.第二个方法是接收要删除的结点,以及遍历的上一个结点值

//这个方法是用来找到要删除的结点,并调用删除结点方法

public boolean remove(int val)
{
    //当二叉搜索树为空树,则返回false
    if (root==null)
    {
        return false;
    }
    //让root赋值给cur去遍历二叉搜索树
    TreeNode cur=root;
    //设置parent记录上一个遍历的结点
    TreeNode parent=null;
    //当cur不等于空就继续找删除结点
    while (cur!=null) {
        //如果cur的val值比删除值小,则让parent记录当前cur结点,并且cur等于cur的右子树
        if (cur.val < val) {
            parent=cur;
            cur = cur.right;
        }
        //如果cur的val值比删除值大,则让parent记录当前cur结点,并且cur等于cur的左子树
        else if (cur.val > val) {
            parent=cur;
            cur = cur.left;
        }
        //如果cur的val值等于删除值,则说明cur所在就是要删除的结点
        // 则调用remoNode方法,传入删除结点cur和parent
        else {
            removeNode(cur,parent);
            return true;
        }

    }
    //当cur等于空就说明二叉搜索树中不存在删除结点,返回false
    return false;
}

//这个方法负责接收要删除的结点和上一个到达的结点,并删除结点值

private void removeNode(TreeNode cur,TreeNode parent)
{
    //一.如果要删除结点的左子树为空(三种情况)
    if (cur.left==null)
    {
        //1.如果根结点等于要删除结点cur
        if (root==cur)
        {
            //让root指向root的右子树
            root=root.right;
        }
        //2.如果cur为parent的左子树
        else if (cur==parent.left)
        {
            //则让parent的左子树指向cur.right的右子树
            parent.left=cur.right;
        }
        //3.如果cur为parent的右子树
        else {
            //则让parent的右子树指向cur的右子树
            parent.right=cur.right;
        }
    }
    //二.当要删除结点cur的右子树为空时(三种情况)
    else if (cur.right==null)
    {
        //1.如果cur等于根结点
        if (cur==root)
        {
            //让根结点指向cur的左子树
            root=cur.left;
        }
        //2.如果cur等于parent的左子树
        else if(cur==parent.left)
        {
            //则让parent的左子树指向cur的左子树
            parent.left=cur.left;
        }
        //3.如果cur等于parent的右子树
        else {
           //则让parent的右子树指向cur的左子树
            parent.right=cur.left;
        }
    }
    //三.如果左子树右子树都不为空
    else {
        //设置getParent指向cur,设置get指向cur的右子树
        TreeNode getParent=cur;
        TreeNode get=cur.right;
        //如果get的左子树不为空,就去找到cur.right的最深左结点,并让getPatent记录上一个到达的结点
        while (get.left!=null)
        {
            getParent=get;
            get=get.left;
        }
        //当get左子树为空,说明找到了最深左结点,让get的val覆盖cur的val
        cur.val=get.val;
        //如果cur.right有左子树,getParent的左子树一定会等于get结点
        if (getParent.left==get)
        {
            //get不可能有左子树了,所以直接让getParent左子树指向get的右子树,图中第一种情况
            getParent.left=get.right;
        }
        //如果cur.right没有左子树,直接让getParent的右子树指向get的右子树即可,图中第二种情况
        else {
            getParent.right=get.right;
        }
    }
}

小结

今天是真的超级努力

早上从10点多起床,洗漱然后吃饭,从十一点半学到了现在,七个多小时,晚上还有课三个小时

最热爱的一集!!

麻烦喜欢的家人们给个三连好嘛!!!(点赞关注收藏!!!)

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/488260