Java 二叉搜尋樹 (BST) 完整實現：插入、查找、刪除、三種遍歷 (遞歸/迭代) 與 JUnit 測試

前言

二叉搜尋樹 (Binary Search Tree, BST) 是基礎資料結構，支援 O(log n) 平均插入、查找、刪除。本文提供生產級 Java 實現：節點類、BST 核心操作、前/中/後序遍歷 (遞歸與迭代雙版本)、完整測試代碼，並解析關鍵邏輯。

一、節點定義

public class TreeNode {
    public Integer data;
    public TreeNode left, right, parent; // 父指針便於刪除操作
    public TreeNode(Integer data) { this.data = data; }
    @Override public String toString() { return "TreeNode[" + data + "]"; }
}

二、BST 核心類

public class SearchTree {
    public TreeNode root;
    public long size;

    /** 插入：不允許重複鍵 */
    public Boolean addTreeNode(Integer data) {
        if (root == null) { root = new TreeNode(data); size++; return true; }
        TreeNode cur = root, parent = null;
        while (cur != null) {
            parent = cur;
            if (data < cur.data) cur = cur.left;
            else if (data > cur.data) cur = cur.right;
            else return false; // 重複
        }
        TreeNode node = new TreeNode(data);
        node.parent = parent;
        if (data < parent.data) parent.left = node;
        else parent.right = node;
        size++;
        return true;
    }

    /** 查找 */
    public TreeNode findTreeNode(Integer data) {
        TreeNode cur = root;
        while (cur != null) {
            if (data < cur.data) cur = cur.left;
            else if (data > cur.data) cur = cur.right;
            else return cur;
        }
        return null;
    }
    // 刪除操作見下文完整代碼...
}

三、三種遍歷：遞歸 vs 迭代 (棧模擬)

3.1 迭代版代碼片段 (中序為例)

public static void medOrderIter(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) { stack.push(cur); cur = cur.left; }
        cur = stack.pop();
        System.out.print(cur.data + " ");
        cur = cur.right;
    }
}

3.2 後序迭代 (單棧 + prev)

public static void postOrderIter(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root, prev = null;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) { stack.push(cur); cur = cur.left; }
        cur = stack.peek();
        if (cur.right == null || cur.right == prev) {
            System.out.print(cur.data + " ");
            stack.pop();
            prev = cur;
            cur = null;
        } else {
            cur = cur.right;
        }
    }
}

四、刪除節點完整邏輯 (三種情況)

1. 葉子節點：直接斷開父指針
2. 單子節點：用子節點頂替
3. 雙子節點：找中序前驅 (左子樹最右) 或中序後繼 (右子樹最左)，複製其值，遞歸刪除該前驅/後繼 (必屬情況 1 或 2)

public boolean delete(Integer data) {
    TreeNode node = findTreeNode(data);
    if (node == null) return false;
    // 情況 1 & 2：至多一個子節點
    TreeNode child = (node.left != null) ? node.left : node.right;
    if (child != null) {
        child.parent = node.parent;
        if (node.parent == null) root = child;
        else if (node == node.parent.left) node.parent.left = child;
        else node.parent.right = child;
    } else { // 葉子
        if (node.parent == null) root = null;
        else if (node == node.parent.left) node.parent.left = null;
        else node.parent.right = null;
    }
    // 情況 3：雙子節點
    if (node.left != null && node.right != null) {
        TreeNode pred = node.left;
        while (pred.right != null) pred = pred.right; // 中序前驅
        node.data = pred.data; // 複製值
        return delete(pred.data); // 遞歸刪除前驅 (必為情況 1/2)
    }
    size--;
    return true;
}

五、測試驗證

public class SearchTreeTest {
    public static void main(String[] args) {
        SearchTree tree = new SearchTree();
        int[] data = {50, 80, 20, 60, 10, 30, 70, 90, 100, 40};
        for (int v : data) tree.addTreeNode(v);

        System.out.println("=== 遞歸前序 ==="); TreeOrder.preOrderRec(tree.root);
        System.out.println("\n=== 迭代前序 ==="); TreeOrder.preOrderIter(tree.root);
        System.out.println("\n=== 遞歸中序 (應有序) ==="); TreeOrder.inOrderRec(tree.root);
        System.out.println("\n=== 迭代中序 ==="); TreeOrder.inOrderIter(tree.root);
        System.out.println("\n=== 遞歸後序 ==="); TreeOrder.postOrderRec(tree.root);
        System.out.println("\n=== 迭代後序 ==="); TreeOrder.postOrderIter(tree.root);

        System.out.println("\n查找 100: " + tree.findTreeNode(100));
        System.out.println("查找 999: " + tree.findTreeNode(999));

        tree.delete(20); // 刪除有雙子節點
        System.out.println("\n刪除 20 後中序:"); TreeOrder.inOrderIter(tree.root);
    }
}

六、輸出結果片段

遞歸中序 (應有序): 10 20 30 40 50 60 70 80 90 100
迭代中序: 10 20 30 40 50 60 70 80 90 100
查找 100: TreeNode[100]
查找 999: null
刪除 20 後中序: 10 30 40 50 60 70 80 90 100

七、複雜度與注意事項

生產建議：直接使用 java.util.TreeMap / TreeSet (紅黑樹實現)，除非教學、面試或極特定定製需求。