如何使用Java函数实现搜索二叉树

搜索二叉树（Binary Search Tree，BST）是一种经典的数据结构，它具有高效的查找、插入、删除等操作时间复杂度，常用于实现关联数据的存储与查询。Java 语言提供了多种数据结构和算法的标准实现（如 TreeMap、HashSet 等），也支持自定义实现 BST。本文将介绍如何使用 Java 函数实现搜索二叉树，包括 BST 的定义、插入、查询、删除等操作。

1. BST 的定义

BST 是一种二叉树，每个节点都包含一个值和两个指向左右子节点的指针。它的特殊之处在于，对于每个节点，左子树中所有节点的值都小于该节点的值，右子树中所有节点的值都大于该节点的值。因此，可以使用 BST 实现快速地查找某个值，或者在已有的数据集合中插入或删除某个值。

在 Java 中，可以定义一个 BST 节点类：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

对于 BST 而言，可以定义一个 BST 类。它包含一个根节点，支持插入、查找、删除等操作：

public class BST {
    private TreeNode root;
    
    //插入操作
    public void insert(int val) { ... }
    
    //查找操作
    public boolean search(int val) { ... }
    
    //删除操作
    public void delete(int val) { ... }
}

2. 插入操作

对于插入操作而言，可以遍历树，找到合适的位置插入新节点。插入操作的实现流程如下：

- 首先，从根节点开始遍历 BST。

- 如果 BST 为空，则将新节点插入到根节点。

- 如果新节点的值小于当前节点的值，则向左子树遍历。

- 如果新节点的值大于当前节点的值，则向右子树遍历。

- 重复上述步骤，直到找到不为空的位置，将新节点插入到该节点处。

对应的 Java 代码如下：

    public void insert(int val) {
        if (root == null) {
            root = new TreeNode(val);
            return;
        }
        TreeNode node = root;
        while (true) {
            if (val < node.val) {
                if (node.left == null) {
                    node.left = new TreeNode(val);
                    break;
                }
                node = node.left;
            } else {
                if (node.right == null) {
                    node.right = new TreeNode(val);
                    break;
                }
                node = node.right;
            }
        }
    }

3. 查找操作

对于查找操作而言，可以遍历树，查找对应的节点。查找操作的实现流程如下：

- 首先，从根节点开始遍历 BST。

- 如果当前节点为空，则返回查找失败。

- 如果查找的值等于当前节点的值，则返回查找成功。

- 如果查找的值小于当前节点的值，则向左子树遍历。

- 如果查找的值大于当前节点的值，则向右子树遍历。

- 重复上述步骤，直到找到对应节点为止。

对应的 Java 代码如下：

    public boolean search(int val) {
        TreeNode node = root;
        while (node != null) {
            if (val == node.val) {
                return true;
            } else if (val < node.val) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        return false;
    }

4. 删除操作

对于删除操作而言，需要考虑多种情况，如删除的节点是否为叶子节点、是否有一个子节点、是否有两个子节点等。删除操作的实现流程如下：

- 首先，从根节点开始遍历 BST。

- 如果当前节点为空，则返回删除失败。

- 如果需要删除的值小于当前节点的值，则向左子树遍历。

- 如果需要删除的值大于当前节点的值，则向右子树遍历。

- 如果需要删除的值等于当前节点的值：

（1）如果当前节点是叶子节点，则直接删除该节点；

（2）如果当前节点有一个子节点，则用该子节点替换当前节点；

（3）如果当前节点有两个子节点，则找到右子树中的最小节点，用其替换当前节点，并删除该最小节点。

- 重复上述步骤，直到找到需要删除的节点。

对应的 Java 代码如下：

    public void delete(int val) {
        TreeNode parent = null;
        TreeNode node = root;
        while (node != null && node.val != val) {
            parent = node;
            if (val < node.val) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        if (node == null) return; // not found
        if (node.left == null && node.right == null) {
            if (node == root) {
                root = null;
            } else if (node == parent.left) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        } else if (node.left == null) {
            if (node == root) {
                root = node.right;
            } else if (node == parent.left) {
                parent.left = node.right;
            } else {
                parent.right = node.right;
            }
        } else if (node.right == null) {
            if (node == root) {
                root = node.left;
            } else if (node == parent.left) {
                parent.left = node.left;
            } else {
                parent.right = node.left;
            }
        } else {
            TreeNode minNode = node.right;
            while (minNode.left != null) {
                minNode = minNode.left;
            }
            int minVal = minNode.val;
            delete(minVal);
            node.val = minVal;
        }
    }

5. 测试

可以编写一个主函数，测试 BST 的基本操作：

public static void main(String[] args) {
    BST bst = new BST();
    bst.insert(5);
    bst.insert(3);
    bst.insert(2);
    bst.insert(4);
    bst.insert(7);
    bst.insert(6);
    bst.insert(8);
    System.out.println(bst.search(5)); // true
    System.out.println(bst.search(2)); // true
    System.out.println(bst.search(9)); // false
    bst.delete(2);
    bst.delete(5);
    System.out.println(bst.search(2)); // false
    System.out.println(bst.search(5)); // false
    System.out.println(bst.search(3)); // true
}

测试结果如下：

true
true
false
false
false
true