二叉排序树的删除方法(思维导图一目了然！！！)

冷不防 2022-11-20 09:33 215阅读 0赞

### 文章目录 ###

*   *   *  二叉排序树的定义
         *  节点类
         *  二叉排序树类
         *  三种删除情况
         *   *  1.删除叶节点
             *  2.删除只有一个孩子节点的非叶节点
             *  3.删除有两个孩子节点的非叶节点
             *  完整代码及测试

### 二叉排序树的定义 ###

根据二叉排序树的定义 百科上有这几个  
![在这里插入图片描述][20201028092903821.png_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center]  
这里我采用了第一种 没有键值对相等的节点 这样好做区分 便于理解 若有多个相同的则会造成影响了

### 节点类 ###

class Node { 
        Node left;
        Node right;
        int value;
    
    
        /** * 插入方法 判断插入的元素比根节点大还是小 小放左边 大放右边 为空直接作为根节点 * * @param node 待插入的节点 */
        public void add(Node node) { 
            if (node == null) { 
                return;
            }
            if (node.value < this.value) { 
                //放左边
                if (this.left == null) { 
                    this.left = node;
                } else { 
                    this.left.add(node);
                }
            } else { 
                //相等或大于就放右边
                if (this.right == null) { 
                    this.right = node;
                } else { 
                    this.right.add(node);
                }
            }
        }
    
    
       
    
        /** * 中序遍历方法 */
        public void midface() { 
            if (this.left != null) { 
                this.left.midface();
            }
            System.out.print(this.value+" ");
            if (this.right != null) { 
                this.right.midface();
            }
        }
    
    
        public Node(int value) { 
            this.value = value;
        }
    
        @Override
        public String toString() { 
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    }

### 二叉排序树类 ###

class BinarySortTree { 
        Node root;
    
        /** * 二叉树添加节点方法 为空直接替换根节点 * * @param node */
        public void add(Node node) { 
            if (root == null) { 
                root = node;
            } else { 
                root.add(node);
            }
    
        }
    
        /** * 遍历树 */
        public void list() { 
            if (root != null) { 
                root.midface();
            }
        }
    
    
    }

暂时只有插入的方法 而我们要做删除前 必须要先找到该元素

且还需要找到该节点的父节点 为删除做准备

所以新增查找方法

/** * @param value 要查找的值 * @return 返回该节点 */
        public Node search(int value) { 
            if (value == this.value) { 
                return this;
            } else if (value < this.value) { 
                //往左递归查找
                if (this.left == null) { 
                    return null;
                }
                return this.left.search(value);
            } else { 
                //往右递归查找
                if (this.right == null) { 
                    return null;
                }
                return this.right.search(value);
            }
        }
    
        /** * @param value 要查找的值的父节点 * @return 返回该节点 * 分几种情况 * 当前节点就是要找的待删的点 即根节点 所以没有父节点 这个最后处理 不在这里写 * 否则如果左子节点不为空 往左递归查找 * 右子节点不为空 往右递归查找 */
        public Node getParent(int value) { 
            if (this.left != null && this.left.value == value || this.right != null && this.right.value == value) 		                    { 
               return this;
            } else { 
                //当前值比要找的值大 那么就需要往左找 注意 必须是有左子树的情况下
                if (this.value > value && this.left != null) { 
                    return this.left.getParent(value);
                    //否则就往右找
                } else if (this.value < value && this.right != null) { 
                    return this.right.getParent(value);
                } else { 
                    return null;
                }
            }
        }

补全二叉查找树的查找方法

/** * 查找要删除的节点 * * @param value * @return */
        public Node search(int value) { 
            if (root == null) { 
                return null;
            } else { 
                return root.search(value);
            }
        }
    
        /** * 查找要删除的父节点 * * @param value * @return */
        public Node searchParent(int value) { 
            if (root == null) { 
                return null;
            } else { 
                return root.getParent(value);
            }
        }

--------------------

### 三种删除情况 ###

接下来看一下图 分三种情况删除

![在这里插入图片描述][20201028090840388.png_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center]

#### 1.删除叶节点 ####

大家先看下总体思路 可以保存下做个记录哦

这是删除叶子节点的代码 对照着思维导图 应该很清晰了

我再截下图  
![在这里插入图片描述][20201028094249429.png_pic_center]

/** * 删除指定value的节点 */
        public void delete(int value) { 
        	//注意 二叉树不能没有根节点哦
            if (root == null) { 
                return;
            } else { 
            	//该方法上面已实现 就是找到目标节点
                Node target = search(value);
                //如果没找到目标节点 则返回
                if (target == null) { 
                    return;
                } else { 
                    //如果找到了目标 则要先判断目标是没有孩子节点的 第一种情况
                    //且要通过他的父节点来删除他
                    Node parent = searchParent(value);
                    //判断无孩子节点
                    if (target.left == null && target.right == null) { 
                    	//注意 需要对根节点做处理
                        //如果无父节点 则证明只有一个根节点 直接置空
                        if (parent == null) { 
                            root = null;
                            return;
                        }
                        //有父节点的情况下
                        //判断父节点的左子节点是不是不为空 且值为 目标值 置空
                        if (parent.left != null && parent.left.value == target.value) { 
                            parent.left = null;
                             //判断父节点的右子节点是不是不为空 且值为 目标值 置空
                        } else if (parent.right != null && parent.right.value == target.value) { 
                            parent.right = null;
                        }
                        //有孩子节点 又要分两种情况讨论 有一个孩子 两个孩子
                    }
    					
    
    
    
    
    					// 这里为后面两种情况的代码
    					//.......................
    				
    
    
    
    
    
                    }
                }
            }
        }

--------------------

#### 2.删除只有一个孩子节点的非叶节点 ####

![在这里插入图片描述][20201028094226511.png_pic_center]

//这里是第三种情况 先写着 因为出了有两个孩子的 无孩子的 剩下的就是只有一个孩子的 节省代码量
    	else if(target.left!=null && target.right!=null){ 
                    //后面实现。。。。。。。。。。。。。。。。。。。。。。。。
                    }else { 
                        //排除了上面两种情况 剩下target必定只有一个孩子节点
                        if (target.left != null) { 
                            //先要判断要删除的节点还有没有父节点 若没有 则自己的左节点成为根节点
                            if (parent == null) { 
                                root = target.left;
                                return;
                            }
                            //先判断parent左子节点为不为空 且target长在左边
                            if (null != parent.left && value == parent.left.value) { 
                                parent.left = target.left;
                            } else { 
                                //否则target长在了右边
                                parent.right = target.left;
                            }
                        } else { 
                            //先要判断要删除的节点还有没有父节点 若没有 则自己的右节点成为根节点
                            if (parent == null) { 
                                root = target.right;
                                return;
                            }
                            //先判断parent左子节点为不为空 且target长在左边
                            if (null != parent.left && value == parent.left.value) { 
                                parent.left = target.right;
                            } else { 
                                //否则target长在了右边
                                parent.right = target.right;
                            }
                        }
    
    
                    }

--------------------

#### 3.删除有两个孩子节点的非叶节点 ####

![在这里插入图片描述][20201028094407955.png_pic_center]  
我选用了找前驱节点并替换的方法

实现

/** * 以当前节点为根节点 找到该左子树下的最大节点 * ps 其实找该右子树下的最小节点也行 * 都是为了替换有两个孩子节点时的情况 * @return 删除返回该节点的值 */
        public int getMax(Node root){ 
            Node node=root.left;
            //找到该左子树下的最大节点
            while(node.right!=null){ 
                node=node.right;
            }
            //如果直接删除 似乎会有瑕疵 因为找到的这个节点可能下面没有节点
            //也可能还有个左子节点 不会出现第三种情况
            //所以要先保存该值 后调用删除方法
            int temp=node.value;
            delete(temp);
            return temp;
        }

有点取巧的感觉

这里有细节需要注意 目标节点的前驱节点 可能有两种情况

1.无孩子节点 直接删除就行了

2.只有一个孩子节点 那就得将孩子节点的位置也移动

3.没有第三种情况 因为在循环下会一直往下找

所以调用delete方法 不会发生一直调用的情况哦！！！

空白处代码只需要添加这两句话 直接修改对应的节点value即可

int temp = getMax(target);
                        //这里不删除 只改变了他的值
                        target.value=temp;

--------------------

#### 完整代码及测试 ####

完整代码放上

package cn.bb.sorttree;
    
    /** * @program: datastructure * @description: 二叉排序树 * @author: sharpbb * @create: 2020-10-26 07:53 **/
    
    public class BinarySortTreeDemo { 
        public static void main(String[] args) { 
            int[] arr = { 7, 3, 10, 12, 5, 1, 9, 2};
            BinarySortTree tree = new BinarySortTree();
            for (int i = 0; i < arr.length; i++) { 
                tree.add(new Node(arr[i]));
            }
            tree.delete(1);
            tree.list();
            System.out.println();
            tree.delete(7);
            tree.list();
            System.out.println();
            tree.delete(3);
            tree.list();
            System.out.println();
            tree.delete(10);
            tree.list();
            System.out.println();
            tree.delete(2);
            tree.list();
            System.out.println();
            tree.delete(12);
            tree.list();
            System.out.println();
            tree.delete(9);
            tree.list();
            System.out.println();
            tree.delete(5);
            tree.list();
        }
    }
    //放上打印结果
    
    /** * 2 3 5 7 9 10 12 * 2 3 5 9 10 12 * 2 5 9 10 12 * 2 5 9 12 * 5 9 12 * 5 9 * 5 */
    
    class BinarySortTree { 
        Node root;
    
        /** * 二叉树添加节点方法 为空直接替换根节点 * * @param node */
        public void add(Node node) { 
            if (root == null) { 
                root = node;
            } else { 
                root.add(node);
            }
    
        }
    
        /** * 遍历树 */
        public void list() { 
            if (root != null) { 
                root.midface();
            }
        }
    
        /** * 查找要删除的节点 * * @param value * @return */
        public Node search(int value) { 
            if (root == null) { 
                return null;
            } else { 
                return root.search(value);
            }
        }
    
        /** * 查找要删除的父节点 * * @param value * @return */
        public Node searchParent(int value) { 
            if (root == null) { 
                return null;
            } else { 
                return root.getParent(value);
            }
        }
    
        /** * 以当前节点为根节点 找到该左子树下的最大节点 * ps 其实找该右子树下的最小节点也行 * 都是为了替换有两个孩子节点时的情况 * @return 删除返回该节点的值 */
        public int getMax(Node root){ 
            Node node=root.left;
            //找到该左子树下的最大节点
            while(node.right!=null){ 
                node=node.right;
            }
            //如果直接删除 似乎会有瑕疵 因为找到的这个节点可能下面没有节点
            //也可能还有个左子节点 不会出现第三种情况
            //所以要先保存该值 后调用删除方法
            int temp=node.value;
            delete(temp);
            return temp;
        }
    
        /** * 删除指定value的节点 */
        public void delete(int value) { 
            if (root == null) { 
                return;
            } else { 
                Node target = search(value);
                //如果没找到目标节点 则返回
                if (target == null) { 
                    return;
                } else { 
                    //如果找到了目标 则要先判断目标是没有孩子节点的 第一种情况
                    //且要通过他的父节点来删除他
                    Node parent = searchParent(value);
                    //判断无孩子节点
                    if (target.left == null && target.right == null) { 
                        //如果无父节点 则证明只有一个根节点
                        if (parent == null) { 
                            root = null;
                            return;
                        }
                        //有父节点的情况下
                        //判断父节点的左子节点是不是不为空且值为目标值 右也相同
                        if (parent.left != null && parent.left.value == target.value) { 
                            parent.left = null;
                        } else if (parent.right != null && parent.right.value == target.value) { 
                            parent.right = null;
                        }
                        //有孩子节点 又要分两种情况讨论 有一个孩子 两个孩子
                        //两个孩子的情况
                    } else if(target.left!=null && target.right!=null){ 
                        int temp = getMax(target);
                        //这里不删除 只改变了他的值
                        target.value=temp;
                    }else { 
                        //排除了上面两种情况 剩下target必定只有一个孩子节点
                        if(target.left!=null){ 
                            //先要判断要删除的节点还有没有父节点 若没有 则自己的左节点成为根节点
                            if (parent==null){ 
                                root=target.left;
                                return;
                            }
                            //先判断parent左子节点为不为空 且target长在左边
                            if(null!=parent.left &&value==parent.left.value){ 
                                parent.left=target.left;
                            }else { 
                                //否则target长在了右边
                                parent.right=target.left;
                            }
                        }else { 
                            //先要判断要删除的节点还有没有父节点 若没有 则自己的右节点成为根节点
                            if (parent==null){ 
                                root=target.right;
                                return;
                            }
                            //先判断parent左子节点为不为空 且target长在左边
                            if(null!=parent.left &&value==parent.left.value){ 
                                parent.left=target.right;
                            }else { 
                                //否则target长在了右边
                                parent.right=target.right;
                            }
                        }
    
    
                    }
                }
            }
        }
    }
    
    class Node { 
        Node left;
        Node right;
        int value;
    
    
        /** * 插入方法 判断插入的元素比根节点大还是小 小放左边 大放右边 为空直接作为根节点 * * @param node 待插入的节点 */
        public void add(Node node) { 
            if (node == null) { 
                return;
            }
            if (node.value < this.value) { 
                //放左边
                if (this.left == null) { 
                    this.left = node;
                } else { 
                    this.left.add(node);
                }
            } else { 
                //相等或大于就放右边
                if (this.right == null) { 
                    this.right = node;
                } else { 
                    this.right.add(node);
                }
            }
        }
    
    
        /** * @param value 要查找的值 * @return 返回该节点 */
        public Node search(int value) { 
            if (value == this.value) { 
                return this;
            } else if (value < this.value) { 
                //往左递归查找
                if (this.left == null) { 
                    return null;
                }
                return this.left.search(value);
            } else { 
                //往右递归查找
                if (this.right == null) { 
                    return null;
                }
                return this.right.search(value);
            }
        }
    
        /** * @param value 要查找的值的父节点 * @return 返回该节点 * 分几种情况 * 当前节点就是要找的待删的点 即根节点 所以没有父节点 这个最后处理 不在这里写 * 否则如果左子节点不为空 往左递归查找 * 右子节点不为空 往右递归查找 */
        public Node getParent(int value) { 
            if (this.left != null && this.left.value == value || this.right != null && this.right.value == value) { 
                return this;
            } else { 
                //当前值比要找的值大 那么就需要往左找 注意 必须是有左子树的情况下
                if (this.value > value && this.left != null) { 
                    return this.left.getParent(value);
                } else if (this.value < value && this.right != null) { 
                    return this.right.getParent(value);
                } else { 
                    return null;
                }
            }
        }
    
    
        /** * 中序遍历方法 */
        public void midface() { 
            if (this.left != null) { 
                this.left.midface();
            }
            System.out.print(this.value+" ");
            if (this.right != null) { 
                this.right.midface();
            }
        }
    
    
        public Node(int value) { 
            this.value = value;
        }
    
        @Override
        public String toString() { 
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    }

**ps：自律的最高境界 就是享受孤独**

[20201028092903821.png_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/e749cce58e64427297b7059c242cc4db.png
[20201028090840388.png_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/6b124cd9ea964533b6bf47e655f3fea1.png
[20201028094249429.png_pic_center]: /images/20221120/4d237e78f88349bd91a05065b3a8efee.png
[20201028094226511.png_pic_center]: /images/20221120/886c55251dac480aad8e0f767301561b.png
[20201028094407955.png_pic_center]: /images/20221120/1692daa59dc44fc499d76479bbd32228.png