Binary Search Tree in Java

BinarySearchTreeExample.java

import java.util.Random;
import java.util.Scanner;

class BinarySearchTreeNode {
    public int data;
    public BinarySearchTreeNode left;
    public BinarySearchTreeNode right;
}

class BinarySearchTree {
    private BinarySearchTreeNode root;

    public boolean deletedFound = false;

    /**
     * 向二分搜索树中插入一个元素
     * @param data 要插入的元素
     */
    public void insert(int data) {
        if (root == null) { // 如果根节点为空，说明这是第一个元素
            root = new BinarySearchTreeNode(); // 创建一个新的节点作为根节点
            root.data = data; // 设置根节点的数据
        } else { // 否则，向以根节点为起始，向下寻找合适的位置插入元素
            insert(root, data);
        }
    }

    /**
     * 向以 node 为根节点的二分搜索树中插入一个元素
     * @param node 二分搜索树的根节点
     * @param data 要插入的元素
     */
    public void insert(BinarySearchTreeNode node, int data) {
        if (data < node.data) { // 如果要插入的元素比当前节点的元素小
            // 说明要插入的元素应该在当前节点的左子树中
            if (node.left != null) { // 如果左子树不为空，继续向下寻找合适的位置插入元素
                insert(node.left, data);
            } else { // 如果左子树为空，说明找到了合适的位置，直接插入元素
                BinarySearchTreeNode newNode = new BinarySearchTreeNode();
                newNode.data = data;
                node.left = newNode;
            }
        } else if (data > node.data) { // 如果要插入的元素比当前节点的元素大
            // 说明要插入的元素应该在当前节点的右子树中
            if (node.right != null) { // 如果右子树不为空，继续向下寻找合适的位置插入元素
                insert(node.right, data);
            } else { // 如果右子树为空，说明找到了合适的位置，直接插入元素
                BinarySearchTreeNode newNode = new BinarySearchTreeNode();
                newNode.data = data;
                node.right = newNode;
            }
        } else { // 如果要插入的元素和当前节点的元素相等
            // 这是一个二分搜索树，不允许有重复的元素，直接抛出异常
            throw new IllegalArgumentException(String.format(
                "The element %d is already in the binary search tree", data
            ));
        }
    }

    /**
     * 查找以 node 为根节点的二分搜索树（子树）中的最小元素
     * @param node 二分搜索树的根节点
     * @return 二分搜索树中的最小元素
     */
    public BinarySearchTreeNode findMin(BinarySearchTreeNode node) {
        if (node.left == null) { // 如果左子树为空，说明当前节点就是最小元素
            return node;
        } else { // 否则，继续向左子树寻找（更小的元素必定在左子树中）
            return findMin(node.left);
        }
    }

    /**
     * 从二分搜索树中删除一个元素
     * @param data 要删除的元素
     * @return 新的根节点，如果没有找到要删除的元素，返回 null
     */
    public BinarySearchTreeNode delete(int data) {
        return delete(root, data);
    }

    /**
     * 从以 node 为根节点的二分搜索树中删除一个元素
     * @param node 二分搜索树的根节点
     * @param data 要删除的元素
     * @return 新的根节点，如果没有找到要删除的元素，返回 null
     */
    public BinarySearchTreeNode delete(BinarySearchTreeNode node, int data) {
        deletedFound = false; // 默认没有找到要删除的元素

        if (node == null) { // 如果当前节点为空，说明没有找到要删除的元素
            return null;
        }

        if (data < node.data) {
            // 如果要删除的元素比当前节点的元素，继续向左子树寻找，直到找到要删除的元素
            // 并将新的，删除了要删除的元素的左子树赋值给当前节点的左子树
            node.left = delete(node.left, data);
        } else if (data > node.data) {
            // 如果要删除的元素比当前节点的元素，继续向右子树寻找，直到找到要删除的元素
            // 并将新的，删除了要删除的元素的右子树赋值给当前节点的右子树
            node.right = delete(node.right, data);
        } else { // 如果找到了要删除的元素
            if (node.left != null && node.right != null) { // 如果要删除的节点同时有左右节点
                // 找到右子树中的最小节点
                BinarySearchTreeNode minNode = findMin(node.right);

                // 将当前节点的数据替换为右子树中的最小节点的数据
                node.data = minNode.data;

                // 删除右子树中的最小节点
                node.right = delete(node.right, minNode.data);
            } else if (node.left != null) { // 如果要删除的节点只有左节点
                // 将当前节点替换为左节点，相当于将当前节点删除，并将左节点提升到当前节点的位置
                node = node.left;
            } else if (node.right != null) { // 如果要删除的节点只有右节点
                // 将当前节点替换为右节点，相当于将当前节点删除，并将右节点提升到当前节点的位置
                node = node.right;
            } else { // 如果要删除的节点没有子节点
                node = null; // 直接将当前节点置为空，相当于删除了这个节点
            }

            deletedFound = true; // 标记已经找到并删除了要删除的元素
        }

        return node; // 返回是否删除了元素
    }

    public void inOrder() {
        inOrder(root);
    }

    public void inOrder(BinarySearchTreeNode node) {
        if (node != null) {
            inOrder(node.left);
            System.out.print(node.data + " ");
            inOrder(node.right);
        }
    }
}

public class BinarySearchTreeExample {
    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
//        tree.insert(5);
//        tree.insert(3);
//        tree.insert(7);
//        tree.insert(2);
//        tree.insert(4);
//        tree.insert(6);
//        tree.insert(8);
//        tree.insert(3); // IllegalArgumentException: The element 3 is already in the binary search tree

        Random random = new Random();
        for (int i = 0; i < 16; i++) { // 向二分搜索树中插入 16 个随机数
            try {
                tree.insert(random.nextInt(0, 100)); // 插入 0 到 100 之间的随机数
            } catch (IllegalArgumentException e) { // 如果插入重复的元素，捕获异常，放弃这个元素
                i--; // 将 i 减一，重新插入一个随机数，保证插入 16 个元素
            }
        }

        System.out.println("In-order traversal: ");
        tree.inOrder();
        System.out.println();

        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.print("Enter a number to delete, or type 'exit' to exit: ");
            String input = scanner.next();
            if (input.equals("exit")) {
                break;
            }

            int n = Integer.parseInt(input);
            tree.delete(n);
            if (tree.deletedFound) {
                System.out.println("Deleted " + n);
            } else {
                System.out.println("Not found " + n);
            }

            System.out.println("In-order traversal: ");
            tree.inOrder();
            System.out.println();
        }
    }
}