Java函数实现二叉搜索树的查找、插入、删除

二叉搜索树也称二叉查找树或二叉排序树，是一种特殊的二叉树。在二叉搜索树中，任意节点的左子树上的所有节点的值均小于它，而右子树上的所有节点的值均大于它。同时，左子树和右子树也都是二叉搜索树。

在Java中，实现二叉搜索树的关键是定义节点类和树类。节点类需要存储节点的值以及左右子节点的引用，树类需要存储根节点的引用以及实现查找、插入、删除等基本操作。

1. 定义二叉搜索树节点类

定义节点类时要注意，需要存储节点的值，以及左右子节点的引用。节点类可以采用泛型，以便处理不同类型的值。

class TreeNode<T extends Comparable<T>> {
    T val;
    TreeNode<T> left;
    TreeNode<T> right;

    TreeNode(T val) {
        this.val = val;
        left = null;
        right = null;
    }
}

2. 定义二叉搜索树类

定义二叉搜索树类时，需要存储根节点的引用。树类中定义了查找、插入、删除等基本操作的函数。

class BinarySearchTree<T extends Comparable<T>> {
    private TreeNode<T> root;

    BinarySearchTree() {
        root = null;
    }

    // 查找操作
    public TreeNode<T> search(T val) {
        return search(root, val);
    }

    private TreeNode<T> search(TreeNode<T> root, T val) {
        if (root == null || root.val.compareTo(val) == 0) {
            return root;
        }
        if (root.val.compareTo(val) > 0) {
            return search(root.left, val);
        } else {
            return search(root.right, val);
        }
    }

    // 插入操作
    public void insert(T val) {
        root = insert(root, val);
    }

    private TreeNode<T> insert(TreeNode<T> root, T val) {
        if (root == null) {
            return new TreeNode(val);
        }
        if (root.val.compareTo(val) > 0) {
            root.left = insert(root.left, val);
        } else if (root.val.compareTo(val) < 0) {
            root.right = insert(root.right, val);
        }
        return root;
    }

    // 删除操作
    public void delete(T val) {
        root = delete(root, val);
    }

    private TreeNode<T> delete(TreeNode<T> root, T val) {
        if (root == null) {
            return null;
        }
        if (root.val.compareTo(val) > 0) {
            root.left = delete(root.left, val);
        } else if (root.val.compareTo(val) < 0) {
            root.right = delete(root.right, val);
        } else {
            // 删除的是叶子节点
            if (root.left == null && root.right == null) {
                root = null;
            }
            // 删除的节点只有一个子节点
            else if (root.left == null) {
                root = root.right;
            } else if (root.right == null) {
                root = root.left;
            }
            // 删除的节点有两个子节点
            else {
                TreeNode<T> node = findMin(root.right);
                root.val = node.val;
                root.right = delete(root.right, node.val);
            }
        }
        return root;
    }

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

3. 测试二叉搜索树类

定义完二叉搜索树类后，需要测试其功能是否正常。下面是一个示例程序，演示如何使用二叉搜索树类完成查找、插入、删除等操作。

public class TestBinarySearchTree {
    public static void main(String[] args) {
        BinarySearchTree<Integer> bst = new BinarySearchTree<Integer>();
        bst.insert(5);
        bst.insert(3);
        bst.insert(7);
        bst.insert(1);
        bst.insert(4);
        bst.insert(9);
        System.out.println(bst.search(3));
        System.out.println(bst.search(6));
        bst.delete(5);
        System.out.println(bst.search(5));
    }
}

运行结果如下所示：

TreeNode@15db9742
null
null

从运行结果可以看出，程序成功地执行了查找、插入、删除等操作，验证了我们所定义的二叉搜索树类的正确性。

综上所述，本文介绍了Java如何实现二叉搜索树的查找、插入、删除等基本操作。Java中的二叉搜索树类可以采用泛型，以便处理不同类型的值，可以方便地实现各类应用场景下的需求。