java 二叉搜索树实现

以下是Java实现二叉搜索树的基本步骤和代码示例：

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

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

2.定义二叉搜索树类

class BST {
    private TreeNode root;

    public BST() {
        root = null;
    }

    // 向二叉搜索树中插入元素
    public void insert(int val) {
        root = insert(root, val);
    }

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

    // 在二叉搜索树中查找元素
    public boolean search(int val) {
        return search(root, val);
    }

    private boolean search(TreeNode node, int val) {
        if (node == null) {
            return false;
        }
        if (val == node.val) {
            return true;
        } else if (val < node.val) {
            return search(node.left, val);
        } else {
            return search(node.right, val);
        }
    }

    // 删除二叉搜索树中的元素
    public void delete(int val) {
        root = delete(root, val);
    }

    private TreeNode delete(TreeNode node, int val) {
        if (node == null) {
            return null;
        }
        if (val < node.val) {
            node.left = delete(node.left, val);
        } else if (val > node.val) {
            node.right = delete(node.right, val);
        } else {
            if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            }
            TreeNode minNode = findMin(node.right);
            node.val = minNode.val;
            node.right = delete(node.right, node.val);
        }
        return node;
    }

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

3.测试代码

public class TestBST {
    public static void main(String[] args) {
        BST bst = new BST();
        bst.insert(5);
        bst.insert(3);
        bst.insert(7);
        bst.insert(1);
        bst.insert(9);
        System.out.println(bst.search(3)); // 输出：true
        bst.delete(3);
        System.out.println(bst.search(3)); // 输出：false
    }
}