投稿
  1. 极客之音首页
  2. 后端开发

Java——二叉搜索树（二叉排序树）的查找、插入、删除

飞熊 • • 后端开发 • 阅读 239

梦想不抛弃苦心追求的人，只要不停止追求，你们会沐浴在梦想的光辉之中。再美好的梦想与目标，再完美的计划和方案，如果不能尽快在行动中落实，最终只能是纸上谈兵，空想一番。只要瞄准了大方向，坚持不懈地做下去，才能够扫除挡在梦想前面的障碍，实现美好的人生蓝图。Java——二叉搜索树（二叉排序树）的查找、插入、删除，希望对大家有帮助，欢迎收藏，转发！站点地址：www.bmabk.com，来源：原文

二叉搜索树

概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
1、若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2、若它的右子树不为空，则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树

二叉搜索树中序遍历的结果是一个有序数组

构建一个二叉树
在这里插入图片描述

class Node{
        public int key;
        public int value;
        Node left;
        Node right;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

查找

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

普通的二叉搜索树查找时间复杂度O（N），如果一个二叉搜索树比较平衡 （左右子树高度差<=1为平衡二叉树（AVL树），左右子树高度差越小，越平衡），那么查找效率比较高。
在这里插入图片描述
在这里插入图片描述

  //记录树的根节点，root==null，当前是个空树
    private Node root = null;

    public Node find(int key) {
        Node cur = root;
        while (cur != null){
            if(key < cur.key){
                //左子树中查找
                cur = cur.left;
            }else if(key > cur.key){
                //右子树中查找
                cur = cur.right;
            }else {
                return cur;
            }
        }
        return null;
    }

插入

1、先找到插入位置，先让插入的节点和根节点比较大小，跟之前的查找方式相似。
2、找到合适位置进行节点插入。

新元素被插入之后一定是个叶子节点

在这里插入图片描述
1、先定义一个节点指向根节点，prev初始为空，prev始终指向cur的父节点，查找过程中，当cur为null时，此时就可以认为找到了合适的差插入位置，此时prev指向的节点就是插入位置。

2、之后判断节点是插入到prev的左子树下还是右子树下，让需要插入的节点和prev节点的值进行比较，小于插入左子树，大于插入右子树。
在这里插入图片描述

public Node insert(int key, int value){
        //1、如果树本身是空树，直接让root指向新节点
        if(root == null){
            root = new Node(key, value);
            return root;
        }
        //2、先找到key所在的位置
        Node cur = root;
        Node prev = null;
        while (cur != null){
            if(cur.key > key){
                //继续往左找
                prev = cur;
                cur = cur.left;
            }else if(cur.key < key){
                //继续往右找
                prev = cur;
                cur = cur.right;
            }else {
                //找到了和key相同的元素
                //针对key相同
                // 1、直接插入失败
                // 2、不创建新节点，把当前的节点的value改成新的value（和标准库一致）
                cur.value = value;
                return cur;

            }
        }
        //循环结束，cur为null，直到了合适的插入地点
        //新节点判断大小之后插入到prev节点的下面
        Node newNode = new Node(key, value);
        if(newNode.key < prev.key){
            prev.left = newNode;
        }else {
            prev.right = newNode;
        }
        return newNode;
    }

删除

删除操作进行的时候，需要先找到要删除的元素，删除情况要分多种情况进行讨论。
讨论：
1、先按照cur的左右子树分别为空分成两大类；
2、在每个大类里面。看cur是父亲的左子树还是右子树
下面就罗列出了可能，画圈的的元素表示要删除元素。

（一）、 cur.left == null
1 ) cur ==root
思路：root = cur.right
在这里插入图片描述
2）cur != root，cur是parent的左子树 cur=parent.left
思路：parent.left = cur.right
在这里插入图片描述
3）cur != root,cur是parent.right
思路：parent.right = cur.right
在这里插入图片描述

========================================

（二）、 cur.right == null

1) cur == root
思路 ：root == cur.left
在这里插入图片描述
2）cur != root cur是parent.left
思路：parent = cur.left
在这里插入图片描述
3）cur != root cur是parent.right
思路：parent.right = cur.left
在这里插入图片描述

========================================
（三）、 cur.left ！= null && cur.right != null
在这里插入图片描述
在这里插入图片描述

 private void removeNode(Node cur, Node parent) {
       //左右子树都无归类到1、2中都可
        if(cur.left == null){
            //1、没有左子树
            if(cur == root){
                //1.1如果cur为根节点
                    root = cur.right;
            }else if(cur == parent.left){
                //1。2cur不为根节点而且为parent的左子树
                parent.left = cur.right;
            }else if(cur == parent.right){
               // 1.3cur不为根节点，且为parent的右子树
                parent.right = cur.right;
            }
        }else if(cur.right == null){
            //2、没有右子树
            if(cur == root){
                //2.1如果cur为根节点
                root = cur.left;
            }else if(cur == parent.left){
                //2。2cur不为根节点而且为parent的左子树
                parent.left = cur.left;
            }else if(cur == parent.right){
                // 2.3cur不为根节点，且为parent的右子树
                parent.right = cur.left;
            }

        }else {
            //左右子树都有
            //1、先找到替罪羊节点，同时找到替罪羊的父节点
            Node scapeGoat = cur.right;
            Node scapeGoatParent = cur;
            while (scapeGoat.left != null){
                scapeGoatParent = scapeGoat;
                scapeGoat = scapeGoat.left;
            }
            //循环结束之后，scapeGoat就指向了右子树中的最小值（最左侧节点）
            //2、把替罪羊的节点的key和value设置给cur
            cur.key = scapeGoat.key;
            cur.value = scapeGoat.value;
            //3、删除替罪羊节点
            if(scapeGoat == scapeGoatParent.left){
                scapeGoatParent.left = scapeGoat.right;
            }else {
                scapeGoatParent.right = scapeGoat.right;
            }
        }

注：将查找方法改为boolean类型方便检测
操作：

public class BinarySearTree {
    class Node{
        public int key;
        public int value;
        Node left;
        Node right;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    //记录树的根节点，root==null，当前是个空树
    public Node root = null;

    public boolean find(int key) {
        Node cur = root;
        while (cur != null){
            if(key < cur.key){
                //左子树中查找
                cur = cur.left;
            }else if(key > cur.key){
                //右子树中查找
                cur = cur.right;
            }else {
                return true;
            }
        }
        return false;
    }

    public Node insert(int key, int value){
        //1、如果树本身是空树，直接让root指向新节点
        if(root == null){
            root = new Node(key, value);
            return root;
        }
        //2、先找到key所在的位置
        Node cur = root;
        Node prev = null;
        while (cur != null){
            if(cur.key > key){
                //继续往左找
                prev = cur;
                cur = cur.left;
            }else if(cur.key < key){
                //继续往右找
                prev = cur;
                cur = cur.right;
            }else {
                //找到了和key相同的元素
                //针对key相同
                // 1、直接插入失败
                // 2、不创建新节点，把当前的节点的value改成新的value（和标准库一致）
                cur.value = value;
                return cur;

            }
        }
        //循环结束，cur为null，直到了合适的插入地点
        //新节点判断大小之后插入到prev节点的下面
        Node newNode = new Node(key, value);
        if(newNode.key < prev.key){
            prev.left = newNode;
        }else {
            prev.right = newNode;
        }
        return newNode;
    }

    public void remove(int key){
        //1、首先找到要删除节点的位置，同时记录下父节点位置
        Node cur = root;
        Node parent = null;
        while (cur != null){
            if(cur.key > key){
                //继续往左找
                parent = cur;
                cur = cur.left;
            }else if(cur.key < key){
                //继续往右找
                parent = cur;
                cur = cur.right;
            }else {
                //找到了要删除的节点
                removeNode(cur,parent);
                return;

            }
    }
        //没有找到节点，删除失败
        return;
}

    private void removeNode(Node cur, Node parent) {
       //左右子树都无归类到1、2中都可
        if(cur.left == null){
            //1、没有左子树
            if(cur == root){
                //1.1如果cur为根节点
                    root = cur.right;
            }else if(cur == parent.left){
                //1。2cur不为根节点而且为parent的左子树
                parent.left = cur.right;
            }else if(cur == parent.right){
               // 1.3cur不为根节点，且为parent的右子树
                parent.right = cur.right;
            }
        }else if(cur.right == null){
            //2、没有右子树
            if(cur == root){
                //2.1如果cur为根节点
                root = cur.left;
            }else if(cur == parent.left){
                //2。2cur不为根节点而且为parent的左子树
                parent.left = cur.left;
            }else if(cur == parent.right){
                // 2.3cur不为根节点，且为parent的右子树
                parent.right = cur.left;
            }

        }else {
            //左右子树都有
            //1、先找到替罪羊节点，同时找到替罪羊的父节点
            Node scapeGoat = cur.right;
            Node scapeGoatParent = cur;
            while (scapeGoat.left != null){
                scapeGoatParent = scapeGoat;
                scapeGoat = scapeGoat.left;
            }
            //循环结束之后，scapeGoat就指向了右子树中的最小值（最左侧节点）
            //2、把替罪羊的节点的key和value设置给cur
            cur.key = scapeGoat.key;
            cur.value = scapeGoat.value;
            //3、删除替罪羊节点
            if(scapeGoat == scapeGoatParent.left){
                scapeGoatParent.left = scapeGoat.right;
            }else {
                scapeGoatParent.right = scapeGoat.right;
            }
        }
    }

}

测试：

public class Test {
    private static void preOrder(BinarySearTree.Node root){
        if(root == null){
            return;
        }
        System.out.print(root.key + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
    private static void inOrder(BinarySearTree.Node root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.key + " ");
        inOrder(root.right);
    }

    public static void main(String[] args) {
        BinarySearTree tree = new BinarySearTree();
        int[] array = {1,9,5,2,7,4,6,8};
        for (int i: array) {
            tree.insert(i,32);
        }
        preOrder(tree.root);
        System.out.println();
        inOrder(tree.root);
        System.out.println();
        System.out.println(tree.find(5));
        System.out.println(tree.find(778));
        preOrder(tree.root);
        System.out.println();
        inOrder(tree.root);
        tree.remove(5);
        System.out.println();
        inOrder(tree.root);
        tree.remove(9);
        System.out.println();
        inOrder(tree.root);
        tree.remove(8);
        System.out.println();
        preOrder(tree.root);
        System.out.println();
        inOrder(tree.root);

    }
}

1 9 5 2 4 7 6 8 
1 2 4 5 6 7 8 9 
true
false
1 9 5 2 4 7 6 8 
1 2 4 5 6 7 8 9 
1 2 4 6 7 8 9 
1 2 4 6 7 8 
1 6 2 4 7 
1 2 4 6 7 
Process finished with exit code 0

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/152993.html

赞 (0)
飞熊的头像飞熊bm
0 0

相关推荐

发表回复

登录后才能评论
极客之音——专业性很强的中文编程技术网站，欢迎收藏到浏览器，订阅我们！