申論題

以下是使用 Java 實現的二元搜尋樹類別，包括新增節點、刪除節點以及中序走訪的函式。這個實現遵循了二元搜尋樹的基本原則，並且提供了一個簡單的測試範例以展示如何使用這個類別來完成指定的工作項目。

java
Copy code
class TreeNode {
    int value;
    TreeNode left, right;

    public TreeNode(int value) {
        this.value = value;
        left = null;
        right = null;
    }
}

public class BinarySearchTree {
    TreeNode root;

    public BinarySearchTree() {
        root = null;
    }

    public void insert(int value) {
        root = insertRec(root, value);
    }

    private TreeNode insertRec(TreeNode root, int value) {
        if (root == null) {
            root = new TreeNode(value);
            return root;
        }
        if (value < root.value) {
            root.left = insertRec(root.left, value);
        } else if (value > root.value) {
            root.right = insertRec(root.right, value);
        }
        return root;
    }

    public void remove(int value) {
        root = removeRec(root, value);
    }

    private TreeNode removeRec(TreeNode root, int value) {
        if (root == null) {
            return root;
        }
        if (value < root.value) {
            root.left = removeRec(root.left, value);
        } else if (value > root.value) {
            root.right = removeRec(root.right, value);
        } else {
            if (root.left == null)
                return root.right;
            else if (root.right == null)
                return root.left;

            root.value = minValue(root.right);
            root.right = removeRec(root.right, root.value);
        }
        return root;
    }

    int minValue(TreeNode root) {
        int minValue = root.value;
        while (root.left != null) {
            minValue = root.left.value;
            root = root.left;
        }
        return minValue;
    }

    public void inorder() {
        inorderRec(root);
        System.out.println();
    }

    private void inorderRec(TreeNode root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.value + " ");
            inorderRec(root.right);
        }
    }

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        bst.insert(25);
        bst.insert(15);
        bst.insert(20);
        bst.insert(30);
        bst.insert(40);

        System.out.println("Inorder traversal of the given tree");
        bst.inorder();

        bst.remove(30);
        System.out.println("\nInorder traversal after deleting 30");
        bst.inorder();

        bst.insert(30);
        System.out.println("\nInorder traversal after adding 30");
        bst.inorder();
    }
}
這段代碼首先定義了一個 TreeNode 類別，用於表示二元搜尋樹的節點。然後，BinarySearchTree 類別提供了 insert、remove 和 inorder 函式，以支援在二元搜尋樹中新增和刪除節點，以及以中序走訪樹的功能。main 函式則展示了如何使用這個類別來完成指定的工作項目，包括依序新增節點、中序走訪、刪除節點，再次新增節點，以及最後的中序走訪以顯示最終的樹結構。