二叉搜索树 【数据结构】

x33g5p2x  于2021-11-01 转载在 其他  
字(3.2k)|赞(0)|评价(0)|浏览(403)

概念

二叉搜索树是一种特殊的二叉树

特点

左子树中的值都小于根节点,右子树中的值都大于根节点
故:中序遍历结果就会得到一个有序序列

最大的特点:就是能够高效的进行查找元素
查找过程类似于二分查找:先从根节点出发开始比较,看待查找元素是小于根节点还是大于根节点,进一步决定是去左子树中找,还是右子树
查找的时间复杂度:O(N) (单支树)

解决方案:采取更加平衡的二叉搜索树,AVL树(绝对平衡),红黑树

基本操作

1.插入元素

其实和查找非常相似,需要先找到待插入元素的合适位置
若树为空树,直接插入为根节点即可

对于二叉搜索树来说,插入元素的时候,元素都是被插入到叶子节点上的

2.查找元素

也很简单,简单画图理解即可~

3.删除元素

需要考虑很多种不同的情况:

  • 情况1:待删除元素是父节点的左子树
    且,待删除元素左子树为空,右子树非空

直接让父节点的左子树,指向待删除元素的右子树即可

  • 情况2:待删除元素是父节点的右子树
    待删除元素的左子树为空,右子树非空

直接让父节点的右子树,指向待删除节点的右子树即可

  • 情况3:待删除元素是父节点的左子树
    待删除元素左子树非空,右子树为空

直接将父节点的左子树,指向待删除结点的左子树即可

  • 情况4:待删除元素是父节点的右子树
    待删除元素左子树非空,右子树为空

直接将父节点的右子树,指向待删除结点的左子树即可

  • 情况5:待删除元素是父节点的左子树
    待删除元素左 / 右子树均非空

  • 情况6:待删除元素是父节点的右子树
    待删除元素左 / 右子树均非空

代码实现:

public class BinarySearchTree {
    public static class Node{
        int key;
        Node left;
        Node right;

        public Node(int key) {
            this.key = key;
        }
    }
    // 根节点 root 为null,表示为空树
    private Node root = null;

    //查找操作
    public Node find(int key){
        // 查找 key 是否存在
        // 若存在,返回对应的Node
        // 若不存在,返回null
        Node cur = root;
        while (cur != null){
            if(key < cur.key){
                //此时去左子树中找
                cur = cur.left;
            }
            else if(key > cur.key){
                // 此时去右子树找
                cur = cur.right;
            }
            else{
                // 找到了
                return cur;
            }
        }
        // key 不存在
        return null;
    }

    //插入操作
    public boolean insert(int key){
        // 二叉搜索树中 是不允许存在相同 key 的元素的
        // 若新插入的 key 重复,就插入失败,返回 false
        // 插入成功 返回 true

        // 空树判断
        if(root == null){
            root = new Node(key);
            return true;
        }
        //先找到合适的位置,再去插入元素
        Node cur = root;
        // 让 parent 始终指向 cur 的父节点
        Node parent = null;
        while (cur != null){
            if(key < cur.key){
                parent = cur;
                cur = cur.left;
            }
            else if(key > cur.key){
                parent = cur;
                cur = cur.right;
            }
            else{
                // 某个元素和待插入元素值相同
                return false;
            }
        }
        // 循环结束,cur 指向 null
        // 当前元素就要插到 parent 子树的位置上
        if(key < parent.key){
            parent.left = new Node(key);
        }
        else{
            parent.right = new Node(key);
        }
        return true;
    }

    //删除操作
    public boolean remove(int key){
        // 先找到 待删除节点的位置,再进行删除
        // 找到待删除元素后,再来判断是那种情况
        Node cur = root;
        Node parent = null;
        while (cur != null){
            if(key < cur.key){
                parent = cur;
                cur = cur.left;
            }
            else if(key > cur.key){
                parent = cur;
                cur = cur.right;
            }
            else{
                // 找到了 待删除元素,就是 cur 指向的元素
                removeNode(parent,cur);
                return true;
            }
        }
        return false;
    }
    private void removeNode(Node parent, Node cur) {
        // 1.待删除元素左子树为空
        if(cur.left == null){
            //1.1 若要删除节点为 root
            if(cur == root){
                root = cur.right;
            }
            //1.2 cur 是 parent 的左子树
            else if(cur == parent.left){
                parent.left = cur.right;
            }
            //1.3 cur 是 parent 的右子树
            else{
                parent.right = cur.right;
            }
        }
        // 2.待删除元素右子树为空
        else if(cur.right == null){
            //2.1 若要删除节点为 root
            if(cur == root){
                root = cur.left;
            }
            //2.2 cur 是 parent 的左子树
            else if(cur == parent.left){
                parent.left = cur.left;
            }
            //2.3 cur 是 parent 的右子树
            else{
                parent.right = cur.left;
            }
        }
        // 3.待删除节点有两个子树
        else{
            // ①找到右子树的最小元素 / 左子树的最大元素(替罪羊)
            Node goatParent = cur;
            Node scapeGoat = cur.right;
            while (scapeGoat.left != null){
                goatParent = scapeGoat;
                scapeGoat = scapeGoat.left;
            }
            // 当循环结束时,scapeGoat 指向了右子树中的最小值
            // ②将找到的元素,赋值给待删除节点
            cur.key = scapeGoat.key;
            // ③删除替罪羊节点
            // 替罪羊节点一定没有左子树
            if(scapeGoat == goatParent.left){
                goatParent.left = scapeGoat.right;
            }
            else{
                goatParent.right = scapeGoat.right;
            }
        }
    }
}

插入测试:

public static void main(String[] args) {
    BinarySearchTree tree = new BinarySearchTree();
    tree.insert(9);
    tree.insert(5);
    tree.insert(2);
    tree.insert(7);
    tree.insert(3);
    tree.insert(6);
    tree.insert(8);
    //为了查看树的结构,可以打印树的先序和中序遍历结果
    tree.preOrder(tree.root);
    System.out.println();
    tree.inOrder(tree.root);
}

// 先序遍历
public void preOrder(Node root){
    if(root == null){
        return;
    }
    System.out.print(root.key + " ");
    preOrder(root.left);
    preOrder(root.right);
}
// 中序遍历
public void inOrder(Node root){
    if(root == null){
        return;
    }
    inOrder(root.left);
    System.out.print(root.key + " ");
    inOrder(root.right);
}

输出结果:

根据先 、中序遍历结果,来还原二叉树,得到:

调试代码:

得到的结果和我们图上还原的结果一样

相关文章