java实现二叉搜索树

二叉搜索树是一种常用的数据结构，它是一棵二叉树，且每个节点的值都大于其左子树中任何节点的值，而小于其右子树中任何节点的值。Java可以通过实现一个类来定义二叉搜索树。

首先，可以创建一个名为“Node”的内部类来表示二叉树的节点。该类包含三个属性：节点的值，左子树和右子树。TreeNode类的代码如下：

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

接着，可以定义BinarySearchTree类来表示二叉搜索树。该类包含一个指向根节点的指针，以及实现一些方法来操作二叉搜索树。例如：

class BinarySearchTree {
    Node root;
    
    public BinarySearchTree() {
        root = null;
    }
    
    public void insert(int val) {
        root = insert(root, val);
    }
    
    private Node insert(Node root, int val) {
        if (root == null) {
            root = new Node(val);
            return root;
        }
        
        if (val < root.val) {
            root.left = insert(root.left, val);
        } else if (val > root.val) {
            root.right = insert(root.right, val);
        }
        
        return root;
    }
    
    public Node search(int val) {
        return search(root, val);
    }
    
    private Node search(Node 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);
        }
    }
    
    public void delete(int val) {
        root = delete(root, val);
    }
    
    private Node delete(Node root, int val) {
        if (root == null) {
            return root;
        }
        
        if (val < root.val) {
            root.left = delete(root.left, val);
        } else if (val > root.val) {
            root.right = delete(root.right, val);
        } else {
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }
            
            root.val = minVal(root.right);
            root.right = delete(root.right, root.val);
        }
        
        return root;
    }
    
    private int minVal(Node root) {
        int minVal = root.val;
        while (root.left != null) {
            minVal = root.left.val;
            root = root.left;
        }
        return minVal;
    }
}

此外，BinarySearchTree类还可以实现其他方法，例如在二叉搜索树中找到最小值、找到最大值、遍历二叉搜索树等。通过这些方法，可以更好地操作二叉搜索树，从而实现各种数据存储和查询的需求。