java数据结构之搜索二叉树

我来跟你详细讲解一下 Java 数据结构之搜索二叉树的完整攻略。

什么是搜索二叉树

搜索二叉树 (Search Binary Tree)，又称为二叉搜索树 (Binary Search Tree)，它是一种常见的数据结构，常用于实现排序和查找算法。

搜索二叉树是一种特殊的二叉树，它满足以下条件：

• 每个节点都有一个键值。
• 每个节点的键值均大于其左子树的所有键值。
• 每个节点的键值均小于其右子树的所有键值。
• 左右子树都必须是搜索二叉树。

搜索二叉树的时间复杂度

搜索二叉树的查找、添加和删除操作都比较简单，并且时间复杂度均为 O(log n)，其中 n 为搜索二叉树的节点数。

Java代码示例

节点定义

首先，我们定义一个节点类，包含键值和左右子节点：

public class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

添加新节点

向搜索二叉树中添加新节点，只需要按照搜索二叉树的规则，不断比较节点的键值大小，找到合适的位置插入新节点即可。

public TreeNode insert(TreeNode root, int val) {
    if (root == null) {
        return new TreeNode(val);
    }
    if (val < root.val) {
        root.left = insert(root.left, val);
    } else if (val > root.val) {
        root.right = insert(root.right, val);
    }
    return root;
}

查找节点

查找节点同样也只需要按照搜索二叉树的规则，不断比较节点的键值大小，直到找到对应的节点。

public TreeNode search(TreeNode root, int val) {
    if (root == null || root.val == val) {
        return root;
    }
    if (val < root.val) {
        return search(root.left, val);
    } else {
        return search(root.right, val);
    }
}

删除节点

删除节点需要分三种情况进行处理：

1. 被删除节点为叶子节点，直接删除。
2. 被删除节点只有一个子节点，将子节点替代被删除节点。
3. 被删除节点有两个子节点，先找到该节点右子树的最小节点，将其值替换到被删除节点中，然后删除右子树的最小节点。

public TreeNode delete(TreeNode root, int val) {
    if (root == null) {
        return null;
    }
    if (val = root.val) {
        // 被删除节点为叶子节点或只有一个子节点
        if (root.left == null) {
            return root.right;
        } else if (root.right == null) {
            return root.left;
        }
        // 被删除节点有两个子节点
        TreeNode minNode = findMin(root.right);
        root.val = minNode.val;
        root.right = delete(root.right, minNode.val);
    } else if (val < root.val) {
        root.left = delete(root.left, val);
    } else {
        root.right = delete(root.right, val);
    }
    return root;
}

private TreeNode findMin(TreeNode root) {
    while (root.left != null) {
        root = root.left;
    }
    return root;
}

总结

搜索二叉树是一种非常实用的数据结构，它可以高效地实现插入、查找和删除操作。在实际应用中，搜索二叉树可以用于数据的排序和索引等方面。

以上就是 Java 数据结构之搜索二叉树的完整攻略，希望对你有所帮助。