二叉排序树（BST）

转x33g5p2x  于2022-02-11 转载在 其他  
字(5.6k)|赞(0)|评价(0)|浏览(181)

二叉排序树

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。

二叉树的特点

一棵空树，或者是具有下列性质的二叉树：

  • 若左子树不空，则左子树上所有结点的值均小于它的根结点的值
  • 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
  • 左、右子树也分别为二叉排序树

创建二叉排序树

思路分析

1、判断根节点是否为空，如果为空就将根节点指向要添加的结点
2、如果要添加的结点的值小于当前结点的值就判断当前结点的左子结点是否为空，如果为空就将结点添加带当前结点的左子结点，如果不为空就向左子树递归添加
3、如果要添加的结点的值大于或等于当前结点的值就判断当前结点的右子结点是否为空，如果为空就将结点添加带当前结点的右子结点，如果不为空就向右子树递归添加

代码

public class Node {

    private int value;
    private Node left;
    private Node right;

    public Node(int value){
        this.value = 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 midDisplay(){
        if (this.left != null) {
            this.left.midDisplay();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.midDisplay();
        }
    }

    @Override
    public String toString() {
        return "Node{" + "value=" + value + '}';
    }

 	getter and setter 方法
public class BSTTree {

    private Node root;

    /**
     * 添加结点
     */
    public void addNode(Node node){
        if (root == null) {
            root = node;
        }else {
            root.add(node);
        }
    }

    /**
     * 中序遍历
     */
    public void midShow(){
        if (root != null) {
            root.midDisplay();
        }else {
            System.out.println("树为空");
        }
    }
}

测试类

public class Test {

    public static void main(String[] args) {
        int[] arr = {7,3,10,12,5,1,9,2};
        BSTTree bstTree = new BSTTree();
        /*循环的添加结点到二叉树*/
        for (int i = 0; i < arr.length; i++) {
            bstTree.addNode(new Node(arr[i]));
        }
        /*中序遍历二叉排序树*/
        bstTree.midShow();
    }
}

运行结果

Node{value=1}
Node{value=2}
Node{value=3}
Node{value=5}
Node{value=7}
Node{value=9}
Node{value=10}
Node{value=12}

Process finished with exit code 0

删除结点

思路分析

删除结点分为三种情况

  • 删除的结点是叶子结点
    （1）找到要删除的结点targetNode
    （2）找到要删除的结点的父结点parentNode
    （3）判断targetNode是parentNode的左子结点还是右子结点
    （4）根据(3)删除结点

  • 删除的结点有一颗子树
    （1）找到要删除的结点targetNode
    （2）找到要删除的结点的父结点parentNode
    （3）确定判断targetNode是parentNode的左子结点还是右子结点
    （4）如果targetNode的子结点是左子结点
    （4.1）如果targetNode是parentNode的左子结点 parentNode.left = targetNode.left
    （4.2）如果targetNode是parentNode的右子结点 parentNode.right= targetNode.left
    （5）如果targetNode的子结点是右子结点
    （5.1）如果targetNode是parentNode的左子结点 parentNode.left = targetNode.right
    （5.2）如果targetNode是parentNode的右子结点 parentNode.right= targetNode.right

  • 删除的结点有两颗子树
    （1）找到要删除的结点targetNode
    （2）找到要删除的结点的父结点parentNode
    （3）从targetNode的右子树找到最小的结点（或者左子树最大的结点）
    （4）用临时变量将最小结点的值保存
    （5）删除targetNode的右子树的最小的结点
    （6）将临时变量的值赋值给targetNode

代码实现

在Node类中添加这两个方法

/**
     *  查找要删除的结点
     * @param value 要删除的结点的值
     * @return 找到返回结点 没找到返回null
     */
    public Node search(int value){
        if (value == this.value){
            /*当前结点就是要删除的结点*/
            return this;
        }else if (value < this.value){
            if (this.left != null) {
                return this.left.search(value);
            }else{
                return null;
            }
        }else{
            /*value的值大于当前结点的value*/
            if (this.right != null) {
                return this.right.search(value);
            }else{
                return null;
            }
        }
    }

    /**
     * 查找要删除结点的父结点
     * @param value 要删除的结点的值
     * @return 要删除的结点的父结点
     */
    public  Node searchParent(int value){
        if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
            /*如果当前结点就是要删除的结点的父结点*/
            return this;
        }else{
            /*如果查找的值小于当前结点的值,并且当前结点的左子结点不为空*/
            if(value < this.value && this.left != null) {
                return this.left.searchParent(value);
            }else if(value >= this.value && this.right != null) {
                return this.right.searchParent(value);
            }else{
                /*找不到父节点*/
                return null;
            }
        }
    }

在BSTTree类中添加以下方法

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

    /**
     * 删除结点
     * @param value 要删除的结点的值
     */
    public void deleteNode(int value){
        if (root == null) {
            System.out.println("当前二叉排序树为空");
            return;
        }else{
            Node targetNode = root.search(value);
            if (targetNode == null) {
                System.out.println("找不到该结点");
                return;
            }
            if (root.getLeft() == null && root.getRight() == null){
                /*当前二叉树只有一个根节点*/
                root = null;
                return;
            }
            Node parentNode = searchParent(value);
            /*如果要删除的结点是叶子结点*/
            if (targetNode.getLeft() == null && targetNode.getRight() == null) {
                if ( parentNode.getLeft() !=null && parentNode.getLeft().getValue() == value){
                    parentNode.setLeft(null);
                }else if ( parentNode.getRight() !=null && parentNode.getRight().getValue() == value){
                    parentNode.setRight(null);
                }
            }else if (targetNode.getLeft() != null && targetNode.getRight() != null){
                /*如果要删除的结点是非叶子结点并且有两颗子树*/
                /*找到要删除的结点的右子树的最小值,并且删除最小值的结点（或者左子树的最大值）*/
                int mini = delRightTreeMiniNode(targetNode.getRight());
                /*将右子树的最小值赋值给要删除的结点*/
                targetNode.setValue(mini);
            }else{
                /*如果要删除的结点是非叶子结点并且只有一颗子树*/
                if (parentNode == null){
                    if (root.getLeft() != null){
                        root = root.getLeft();
                        return;
                    }else {
                        root = root.getRight();
                        return;
                    }
                }
                /*如果要删除的结点有左子节点*/
                if (targetNode.getLeft() != null){
                    /*如果要删除的结点是其父结点的左子结点*/
                    if (parentNode.getLeft().getValue() == value){
                        parentNode.setLeft(targetNode.getLeft());
                    }else{/*如果要删除的结点是其父结点的右子结点*/
                        parentNode.setRight(targetNode.getLeft());
                    }
                }else{/*如果要删除的结点有右子节点*/
                    if (parentNode.getLeft().getValue() == value){
                        parentNode.setLeft(targetNode.getRight());
                    }else{/*如果要删除的结点是其父结点的右子结点*/
                        parentNode.setRight(targetNode.getRight());
                    }
                }
            }
        }
    }

    /**
     * 删除以node为根节点的二叉排序树的最小结点
     * @param node 以node为根节点
     * @return 最小的结点的值
     */
    public int delRightTreeMiniNode(Node node){
        Node temp = node;
        while (temp.getLeft() != null){
            temp = temp.getLeft();
        }
        /*这个最小结点一定是叶子结点*/
        deleteNode(temp.getValue());
        return temp.getValue();
    }

测试类

public class Test {

    public static void main(String[] args) {
        int[] arr = {7,3,10,12,5,1,9,2};
        BSTTree bstTree = new BSTTree();
        /*循环的添加结点到二叉树*/
        for (int i = 0; i < arr.length; i++) {
            bstTree.addNode(new Node(arr[i]));
        }
        /*中序遍历二叉排序树*/
        bstTree.midShow();
        bstTree.deleteNode(9);
        bstTree.deleteNode(1);
        bstTree.deleteNode(7);
        System.out.println("------------------");
        bstTree.midShow();
    }
}

运行结果

Node{value=1}
Node{value=2}
Node{value=3}
Node{value=5}
Node{value=7}
Node{value=9}
Node{value=10}
Node{value=12}
------------------
Node{value=2}
Node{value=3}
Node{value=5}
Node{value=10}
Node{value=12}

Process finished with exit code 0

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/m0_60117382/article/details/122850097

内容来源于网络，如有侵权，请联系作者删除！

Java数据结构算法数据结构笔记二叉排序树BST

相关文章

    查看更多
    微信公众号

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com