三、二元搜尋樹（binary search tree）是一種資料經過整理後的二元樹。對於任何一個節點，若左子樹（left subtree）存在，則左子樹所有節點的值均小於自己的值；若右子樹（right subtree）存在，則右子樹所有節點的值均大於自己的值。請用 C++或是 Java 寫一個二元搜尋樹的類別（class），包括新增一個節點（insert）、刪除一個節點（remove）以及中序走訪（inorder）這三個函式（function）並撰寫主程式完成以下工作。（40 分）
工作項目： 
● 依序新增 25, 15, 20, 30, 40 到一個空的二元搜尋樹。
● 以中序走訪此樹 
●  刪除 30 
●  增加 30
●  以中序走訪此樹

詳解 (共 1 筆)

詳解 提供者：hchungw
以下是使用 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 函式則展示了如何使用這個類別來完成指定的工作項目，包括依序新增節點、中序走訪、刪除節點，再次新增節點，以及最後的中序走訪以顯示最終的樹結構。