【Java数据结构】搜索二叉树——对节点的插入、查找、删除 操作（注释很详细我奶奶都能看懂）

📢博客主页：🏀敲代码的布莱恩特🏀
📢欢迎点赞 👍 收藏 ⭐留言 📝 欢迎讨论！👏
📢本文由 【敲代码的布莱恩特】 原创，首发于 CSDN🙉🙉🙉
📢由于博主是在学小白一枚，难免会有错误，有任何问题欢迎评论区留言指出，感激不尽！✨
📖精品专栏（不定时更新）【JavaSE】 【Java数据结构】【LeetCode】

【Java数据结构】搜索二叉树——对节点的插入、查找、删除 操作

🛸搜索二叉树——基本概念

**二叉搜索树又称 **

二叉排序树

，它或者是一棵空树，或者是具有以下性质的二叉树:

1. 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2. 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
3. 它的 左右子树也分别为二叉搜索树

**

注意

：二叉搜索树中没有重复的元素**

如下图为一个二叉搜索树

🛸搜索二叉树——基本属性

**二叉树是由一个一个节点组成的，先定义好

节点的属性

**

代码实现：

publicclassNode{int key;//节点值Node left;//左孩子节点Node right;//右孩子节点publicNode(int key){//重写一下节点的构造方法this.key = key;}}Node root =null;//一开始根节点为空

🛸搜索二叉树——查找节点

查找过程：

1. 拿着待查元素和根节点比较；
2. 如果比根节点小，继续在左子树中查找；
3. 如果比根节点大，继续在右子树中查找；
4. **如果当前元素查找到null也没找到，说明该元素不存在**。

代码实现：

/**
     * 在搜索树中查找 key，如果找到，返回 key 所在的结点，否则返回 null
     * @param key
     * @return
     */publicNodesearch(int key){Node cur = root;//cur从root开始走while(cur !=null){if(cur.key == key){//如果cur的值与key相等，则返回curreturn cur;}elseif(key > cur.key){//key值比cur的值大，cur往右节点走
                cur = cur.right;}elseif(key < cur.key){//key值比cur的值小，cur往左节点走
                cur = cur.left;}}returnnull;//root为空，或者二叉树里没有这个节点，返回空值}

🛸搜索二叉树——插入节点

插入过程：

1. 如果树是空树，即根== null，直接插入即可，返回true
2. 如果树不是空树，按照 查找逻辑（大的放左边，小的放右边）确定插入位置，插入新结点注意：最后确定的插入位置一定是叶子节点

代码实现：

/**
     * 插入
     * @param key
     * @return true 表示插入成功, false 表示插入失败
     */publicBooleaninsert(int key){if(root ==null){//如果根节点空，则第一个节点就是根节点
            root =newNode(key);returntrue;}Node cur = root;//用cur从root位置开始往下走Node parent =null;//需要用一个parent节点来记录上一个节点//通过while循环来找插入位置while(cur !=null){if(key == cur.key){returnfalse;//如果二叉树里已经有这个值，就无法插入}elseif(key < cur.key){//key比cur的值小，说明要插到左边
                parent = cur;//记录上一个节点
                cur = cur.left;//cur往左走}elseif(key > cur.key){//key比cur的值大，说明要插到右边
                parent = cur;//记录上一个节点
                cur = cur.right;//cur往右走}}//while走完了，说明是时候插入节点了，因为我们插入节点的位置一定是叶子节点的位置//这就需要用到parent了Node node =newNode(key);//创建要插入的新节点if(node.key > parent.key){//比parent值大放右边
            parent.right = node;}else{
            parent.left = node;//反之放左边}returntrue;//插入成功}

🛸搜索二叉树——删除节点

设待删除结点为 cur, 待删除结点的双亲结点为 parent，删除节点的关键在于对多种情况的分析

1. cur.left == null**待删除节点只有右子树**（这种情况下删哪个点，就将其右子树接到这个点的父节点后边）
2. cur.right == null待删除节点**只有左子树**（这种情况下删哪个点，就将其左子树接到这个点的父节点后边）
3. cur.left != null && cur.right != null**待删除节点左右子树都存在**（需要使用替换法进行删除，即在它的右子树中寻找最小值结点，用它的值填补到被删除节点中，再来处理该结点的删除问题，关键就在于这个寻找最小值替代这一步）

总而言之，这第三种情况处理方法就是，从待删除点的右树里找最小值来替换待删除点，然后将替罪羊节点的右树接到替罪羊节点的父节点后边即可，注意点就是替罪羊节点是在父节点左边还是右边

代码实现：

/**
     * 删除成功返回 true，失败返回 false
     * @param key
     * @return
     */publicvoidremoveKey(int key){if(root ==null){return;}Node cur = root;Node parent =null;while(cur !=null){if(cur.key == key){remove(parent,cur);return;}elseif(cur.key < key){
                parent = cur;
                cur = cur.right;}else{
                parent = cur;
                cur = cur.left;}}}privatevoidremove(Node parent,Node cur){if(cur.left ==null){//删除只有右孩子的节点if(cur == root){//要删除的点是根节点
                root = cur.right;}elseif(cur == parent.left){//要删除的点在父亲节点左边
                parent.left = cur.right;}elseif(cur == parent.right){//要删除的点在父亲节点右边
                parent.right = cur.right;}}elseif(cur.right ==null){//删除只有左孩子的节点if(cur == root){//要删除的点是根节点
                root = cur.left;}elseif(cur == parent.left){//要删除的点在父亲节点左边
                parent.left = cur.left;}elseif(cur == parent.right){//要删除的点在父亲节点右边
                parent.right = cur.left;}}else{Node target = cur.right;Node targetParent = cur;//找替罪羊target，找右树的最小左子树while(target.left !=null){
                targetParent = target;
                target = target.left;}
            cur.key = target.key;if(target == targetParent.left){//如果当前目标值是父节点的左孩子
                targetParent.left = target.right;//就把目标节点的右孩子接到父节点的左边}elseif(target == targetParent.right){//如果当前目标值是父节点的右孩子
                targetParent.right = target.right;//就把目标节点的右孩子接到父节点的右边}}}

🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙
❤原创不易，如有错误，欢迎评论区留言指出，感激不尽❤
❤ 如果觉得内容不错，给个三连不过分吧~ ❤
❤ 看到会回访~ ❤
🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙