【数据结构-Java】二叉排序树

た入场券 2023-01-11 03:56 183阅读 0赞

### 文章目录 ###

*   *  1、二叉排序树介绍
     *  2、构建二叉排序树
     *  3、二叉排序树删除节点
     *  4、完整代码
     *   *  1、节点类
         *  2、二叉排序树类

## 1、二叉排序树介绍 ##

**二叉排序树**BST: (Binary Sort(Search) Tree), 对于二叉排序树的**任何一个非叶子节点**，要求**左子节点的值比当**

**前节点的值小**，**右子节点的值比当前节点的值大**。

**特别说明**：如果有相同的值，可以将该节点放在左子节点或右子节点

比如针对前面的数据 (7, 3, 10, 12, 5, 1, 9) ，对应的二叉排序树为：

![image.png][]

## 2、构建二叉排序树 ##

/** * 添加节点 * * @param node */
        public void add(Node node) { 
            if (node == null) throw new RuntimeException("节点为空");
            //传入节点的值和当前子树根节点的值比较，比当前值大就往右边比较
            if (node.val >= this.val) { 
                if (this.right == null) { //如果右边为空，则直接挂在右子节点就可以
                    this.right = node;
                } else {  //递归往右子树添加
                    this.right.add(node);
                }
            } else { 
                if (this.left == null) { 
                    this.left = node;
                } else { 
                    this.left.add(node);
                }
            }
        }

## 3、二叉排序树删除节点 ##

思路：

1.  第一栋情况：删除的是叶子节点
    
    1.  先找到需要删除的节点targetNode
    2.  找到targetNode的父结点parent
    3.  确定targetNode是parent的左子节点还是右子节点
    4.  根据前面的情况对应删除

![image.png][image.png 1]

1.  第二种情况：删除的只有一颗子树的节点
    
    1.  先找到需要删除的节点targetNode
    2.  找到targetNode的父结点parent
    3.  确定targetNode的子节点是左子节点还是右子节点
    4.  targetNode是parent的左子节点还是右子节点

![image.png][image.png 2]

1.  第三种情况：删除有两颗子树的节点
    
    1.  先找到需要删除的节点targetNode
    2.  找到targetNode的父结点parent
    3.  从target的右子树中找出最小的节点
    4.  使用临时变量，将最小节点的值temp保存
    5.  删除最小的节点
    6.  将最小节点temp作为根节点保存左子树和右子树

![image.png][image.png 3]

## 4、完整代码 ##

### 1、节点类 ###

/** * 节点类 */
    class Node { 
        int val;//值
        Node left;//左
        Node right;//右
    
        public Node(int val) { 
            this.val = val;
        }
    
        /** * 找到需要删除的节点 * * @param val * @return */
        public Node search(int val) { 
            if (this.val == val) return this;//就是当前节点
            if (this.val <= val) { 
                if (this.right == null) return null;//如果右子树为空，返回空
                return this.right.search(val);
            } else { 
                if (this.left == null) return null;
                return this.left.search(val);
            }
        }
    
        /** * 查找要删除节点的父结点 * * @param val * @return */
        public Node searchParent(int val) { 
            if ((this.left != null && this.left.val == val) || (this.right != null && this.right.val == val)) return this;
            if (this.val <= val) { 
                if (this.right == null) return null;//如果右子树为空，返回空
                return this.right.searchParent(val);
            } else { 
                if (this.left == null) return null;
                return this.left.searchParent(val);
            }
        }
    
    
        /** * 添加节点 * * @param node */
        public void add(Node node) { 
            if (node == null) throw new RuntimeException("节点为空");
            //传入节点的值和当前子树根节点的值比较，比当前值大就往右边比较
            if (node.val >= this.val) { 
                if (this.right == null) { //如果右边为空，则直接挂在右子节点就可以
                    this.right = node;
                } else {  //递归往右子树添加
                    this.right.add(node);
                }
            } else { 
                if (this.left == null) { 
                    this.left = node;
                } else { 
                    this.left.add(node);
                }
            }
        }
    
        /** * 中序遍历 */
        public void infixNode() { 
            if (this.left != null) this.left.infixNode();
            System.out.println(this);
            if (this.right != null) this.right.infixNode();
        }
    
        @Override
        public String toString() { 
            return new StringJoiner(", ", Node.class.getSimpleName() + "[", "]")
                    .add("val=" + val)
                    .toString();
        }
    }

### 2、二叉排序树类 ###

/** * 二叉排序树类 */
    class BSTree { 
        private Node root;
    
        /** * 删除节点 */
        public void delete(int val) { 
            if (root == null) return;
            //1、先找到需要删除的节点
            Node node = search(val);
            //如果没有该节点
            if (node == null) return;
            //如果该二叉排序树只有一个节点，直接删除即可
            if (root.left == null && root.right == null) { 
                root = null;
                return;
            }
            //2、找到需要删除节点的父结点
            Node parent = searchParent(val);
            //3、确定删除节点是否有子树
            //1）没有的节点为叶子节点
            if (node.left == null && node.right == null) { 
                if (parent.right != null && parent.right == node) { 
                    parent.right = null;
                    return;
                }
                if (parent.left != null && parent.left.val == val) { 
                    parent.left = null;
                    return;
                }
                //删除的节点有左右子树均存在
            } else if (node.left != null && node.right != null) { 
                //找到右子树的最小节点，并删除最小节点
                int minValue = delRightTreeMin(node.right);
                node.val = minValue;
            } else { //只有一颗子树
                //此时删除根节点
                if(parent == null){ 
                    if(node.left!=null){ 
                        node.val = node.left.val;
                        node.left = node.left.left;
                        node.right = node.left.right;
                    }else { 
                        node.val = node.right.val;
                        node.left = node.right.left;
                        node.right = node.right.right;
                    }
                    return;
                }
                //如果要删除的节点有左子节点
                if (node.left != null) { 
                    //node是parent的左子节点
                    if (parent.left == node) { 
                        parent.left = node.left;
                    } else { //node是parent的右子节点
                        parent.right = node.left;
                    }
                } else { //要删除的节点有右子节点
                    //node是parent的左子节点
                    if (parent.left == node) { 
                        parent.left = node.right;
                    } else { //node是parent的右子节点
                        parent.right = node.right;
                    }
                }
            }
        }
    
        /** * @param node 传入的节点（当作二叉排序树的根节点） * @return 以node为根节点的二叉排序树最小节点的值并删除这个最小值 */
        public int delRightTreeMin(Node node) { 
            Node target = node;
            //循环查找左节点就会找到最小值
            while (target.left != null) { 
                target = target.left;
            }
            //这是target指向了最小节点
            //删除该最小节点
            delete(target.val);
            return target.val;
        }
    
        /** * 查找要删除的节点 */
        public Node search(int val) { 
            if (root == null) return null;
            return root.search(val);
        }
    
        /** * 查找要删除节点的父结点 */
        public Node searchParent(int val) { 
            if (root == null) return null;
            return root.searchParent(val);
        }
    
        /** * 添加节点 */
        public void add(Node node) { 
            if (root == null) root = node;//说明为空树
            else root.add(node);
        }
    
        /** * 中序遍历 */
        public void infixOrder() { 
            if (root == null) { 
                System.out.println("空树");
                return;
            }
            root.infixNode();
        }
    }

[image.png]: /images/20221119/b1d777a9a06949379395239ca0645ccc.png
[image.png 1]: https://img-blog.csdnimg.cn/img_convert/67ab4062bc28d24206936356832c7b09.png
[image.png 2]: https://img-blog.csdnimg.cn/img_convert/e4b93bcc5a861187ac4896258e6ecc51.png
[image.png 3]: https://img-blog.csdnimg.cn/img_convert/4df499120691ec4ef873454c5a300a27.png