二叉搜索树（二叉排序树）—Java（上）

2023-07-29 116

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 二叉搜索树（二叉排序树）—Java（上）

🔎概念

二叉搜索树又称二叉排序树

可以是一棵空树

也可以不是一棵空树（doge）

上图所示就是一棵二叉搜索树

根节点root值为7，root的左子树的值全部比root的值小，root的右子树的值全部比root的值大

root.left–>root的左子树的根节点4，其左侧节点的值1比4小，右侧节点的值6比4大（但它们均小于7）

root.right–>root的右子树的根节点11，其左侧节点的值9比11小，右侧节点的值13比11大（但它们均大于7）

🔎模拟实现二叉树

🌻find–>查找二叉树中的元素

public TreeNode find(int val) {
        TreeNode cur = root;
        while(cur != null) {
            if(cur.val < val) {
                cur = cur.right;
            }else if(cur.val > val) {
                cur = cur.left;
            }else {//cur.val == val-->find!
                return cur;
            }
        }
        //未找到
        return null;
}

查找二叉搜索树中指定的val值

如果cur节点的值小于要查找的元素的值，cur = cur.right–>去树的右侧查找

如果cur节点的值大于要查找的元素的值，cur = cur.left–>去树的左侧查找

🌻insert–>在二叉树中插入元素

public void insert(int val) {
        if(root == null) {
            root = new TreeNode(val);
            return;
        }
        TreeNode pre = null;//叶子节点
        TreeNode cur = root;
        while(cur != null) {
            pre = cur;
            if(cur.val < val) {
                cur = cur.right;
            }else if(cur.val > val){
                cur = cur.left;
            }else {//二叉搜索树中不要插入相同的数据（无意义）
                return;
            }
        }
        if(val < pre.val) {
            pre.left = new TreeNode(val);
        }else {
            pre.right = new TreeNode(val);
        }
}

如果该搜索树是一棵空树，则插入的元素就是这棵树的root（根节点）

如果不是，在叶子节点的左/右侧插入对应的元素

🌻inorder–>中序遍历二叉树

public void inOrder(TreeNode root) {
        if(root == null) return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
}
• 1
• 2
• 3
• 4
• 5
• 6

🌻remove–>删除二叉树中的元素

cur–>要删除的节点 / pre–>要删除节点的父节点 / root–>根节点

二叉搜索树的删除
cur.left == null–>要删除节点的左侧为空
1)cur是根节点，root = cur.right
2)cur不是根节点，cur是父节点的左,pre.left = cur.right
3)cur不是根节点，cur是父节点的右,pre.right = cur.right
cur.right == null–>要删除节点的右侧为空
1)cur是根节点，root = cur.left
2)cur不是根节点，cur是父节点的左,pre.left = cur.left
3)cur不是根节点，cur是父节点的右,pre.right = cur.left
cur.left != null && cur.right != null–>要删除节点的左右均不为空
1)找cur左子树的右叶子节点–>左子树的最大值–>最大值的右节点一定为null
2)找cur右子树的左叶子节点–>右子树的最小值–>最小值的左节点一定为null
3)不可以是左子树的左叶子节点(左子树最小值) or 右子树的右叶子节点（右子树最大值）