二叉搜索树

时间：2024-11-05 12:58:32

1 概念

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

2.查找

图解：

TreeNode searchBST(TreeNode root, int val){
if（root==null){
return null;
}
if(root.val==val){
return root;
}
while(cur!=null){
if(cur.val>val){
cur=cur.right;
}
else if(cur.val<val){
cur=cur.left;
}
}
return root;
}
如果采用递归操作： 
TreeNode searchBST(TreeNode root, int val) {
    if (root == null) {
        return null;
    }
    // 去左子树搜索
    if (root.val > val) {
        return searchBST(root.left, target);
    }
    // 去右子树搜索
    if (root.val < val) {
        return searchBST(root.right, target);
    }
    return root;//上面两个都不满足，说明root.val == val直接返回root
}

 

3. 操作-插入

具体步骤：

  • insertIntoBST 方法：

    检查树是否为空，如果为空则创建根节点。

  • 使用 while 循环遍历树，找到合适的插入位置。
  • 如果当前节点的值大于 key，则向左子树移动；如果小于，则向右子树移动。
  • 如果发现节点的值与要插入的值相同，则返回根节点，表示不插入相同节点。
  • 将新节点连接到找到的父节点的左或右子树。

采用双指针：

 public TreeNode insertIntoBST(int key) {
        // 如果树为空，创建根节点
        if (root == null) {
            root = new TreeNode(key);
            return root;
        }

        TreeNode cur = root;
        TreeNode parent = null;
        TreeNode node = new TreeNode(key);

        // 查找插入位置
        while (cur != null) {
            parent = cur; // 记录当前节点的父节点
            if (cur.val > key) {
                cur = cur.left; // 向左子树移动
            } else if (cur.val < key) {
                cur = cur.right; // 向右子树移动
            } else {
                return root; // 不允许插入相同的节点
            }
        }

        // 将新节点连接到父节点
        if (parent.val > key) {
            parent.left = node; // 插入到左子树
        } else {
            parent.right = node; // 插入到右子树
        }

        return root; // 返回根节点
    }

采用递归方法：

TreeNode insertIntoBST(TreeNode root, int val) {
    // 找到空位置插入新节点
    if (root == null) 
    return new TreeNode(val);
    //这里就相当于将节点接入到二叉树对应的叶子中
    if (root.val == val) {return root;}
    //BST 中一般不会插入已存在元素
    if (root.val < val) 
        root.right = insertIntoBST(root.right, val);
    if (root.val > val) 
        root.left = insertIntoBST(root.left, val);
    return root;
}

4.删除：

  1. deleteNode 方法：

    • 实现删除节点的逻辑。
    • 如果找到了需要删除的节点，判断其子节点情况：
      • 情况 1：节点没有子节点，直接返回 null。
      • 情况 2：节点只有一个子节点，返回那个子节点。
      • 情况 3：节点有两个子节点，找到右子树的最小节点，替换当前节点，并删除右子树的最小节点。
TreeNode deleteNode(TreeNode root,int val{

if(root==null){return null;}
if(root.val>key){


root.left=deleteNode(root.left,val);
}else if(root.val<key){


root.left=deleteNode(root.right,val);
}

return root;
}

情况 1：A 恰好是末端节点，且左右子节点都为空，则释放当前节点。

if (root.left == null && root.right == null)
    return null;


 情况 2：A 只有一个非空子节点，那么与他的孩子节点互换位置，后是放尾节点。

if (root.left == null) return root.right;
if (root.right == null) return root.left;


 情况 3：A 有两个子节点，麻烦了，为了不破坏 BST 的性质，A 必须找到左子树中最大的那个节点，或者右子树中最小的那个节点互换。

if (root.left!= null && root.right != null) {
    // 找到右子树的最小节点
    TreeNode minNode = getMin(root.right);
    // 把 root 改成 minNode
    root.val = minNode.val;
    // 转而去删除 minNode
    root.right = deleteNode(root.right, minNode.val);
}

三中情况都完成后，整理一下代码：

    // 删除节点方法
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null; // 空树情况

        if (root.val == key) {
            // 情况 1 和 2: 只有一个子节点或没有子节点
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;

            // 情况 3: 两个子节点
            // 获取右子树的最小节点
            TreeNode minNode = getMin(root.right);
            // 删除右子树的最小节点
            root.right = deleteNode(root.right, minNode.val);
            // 用右子树最小的节点替换 root 节点
            minNode.left = root.left;
            minNode.right = root.right;
            root = minNode;
        } else if (root.val > key) {
            root.left = deleteNode(root.left, key); // 在左子树中删除
        } else {
            root.right = deleteNode(root.right, key); // 在右子树中删除
        }
        return root; // 返回更新后的根节点
    }

    // 获取最小节点
    public TreeNode getMin(TreeNode node) {
        // BST 最左边的节点就是最小的节点
        while (node.left != null) node = node.left;
        return node;
    }

到这里竹竹零就要和大家说再见了

9a90bc9fb4c3409c9569951569288f5a.png

希望时光不负赶路人，愿我们做最好的自己！！！

如果您觉得有失偏颇请您在评论区指正，如果您觉得不错的话留个好评再走吧！！

您的鼓励就是对我最大的支持!  ！ ！

相关文章