Java 二叉樹節點刪除：合併刪除法完整實作與圖解

二叉搜尋樹刪除節點的三種情況

刪除二叉搜尋樹（BST）節點時，需維持 BST 性質（左子樹鍵值 < 根 < 右子樹鍵值）。根據節點子樹情況分三類處理：

1. 無右子樹：左子樹直接上接父節點。
2. 無左子樹：右子樹直接上接父節點。
3. 左右子樹皆在：需合併兩棵子樹，常用「前驅節點（左子樹最大）」或「後繼節點（右子樹最小）」替代被刪節點。

合併刪除法核心邏輯

本文採用 左子樹最右節點（最大值）接管右子樹 策略：

1. 找到左子樹中最右節點 maxLeft（無右子節點）。
2. 將被刪節點的右子樹掛在 maxLeft.right。
3. 將左子樹根節點上接父節點。

完整 Java 實作

public class BinarySearchTree {
    private Node root;

    static class Node {
        int key;
        Node left, right;
        Node(int key) { this.key = key; }
    }

    /** 合併刪除法刪除指定鍵值節點 */
    public void deleteByMerging(int key) {
        Node current = root;
        Node parent = null;

        // 1. 尋找目標節點及其父節點
        while (current != null && current.key != key) {
            parent = current;
            if (key < current.key) current = current.left;
            else current = current.right;
        }

        if (current == null) {
            System.out.println("節點 " + key + " 不存在於樹中");
            return;
        }

        Node replacement; // 將替代目標節點的子樹根

        // 2. 三種情況處理
        if (current.right == null) {
            // 無右子樹：左子樹上接
            replacement = current.left;
        } else if (current.left == null) {
            // 無左子樹：右子樹上接
            replacement = current.right;
        } else {
            // 左右子樹皆在：合併刪除
            Node maxLeft = current.left;
            while (maxLeft.right != null) {
                maxLeft = maxLeft.right; // 找左子樹最大節點
            }
            maxLeft.right = current.right; // 右子樹接在最大節點右側
            replacement = current.left;    // 左子樹根作為替代
        }

        // 3. 更新父節點連結
        if (parent == null) {
            root = replacement; // 刪除的是根節點
        } else if (parent.left == current) {
            parent.left = replacement;
        } else {
            parent.right = replacement;
        }
    }

    // 輔助：中序遍歷驗證
    public void inOrder() { inOrder(root); System.out.println(); }
    private void inOrder(Node n) {
        if (n != null) { inOrder(n.left); System.out.print(n.key + " "); inOrder(n.right); }
    }

    // 測試
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        // 建構測試樹
        int[] keys = {50, 30, 70, 20, 40, 60, 80, 35};
        for (int k : keys) bst.insert(k); // 需自行實作 insert

        System.out.print("刪除前中序："); bst.inOrder(); // 20 30 35 40 50 60 70 80
        bst.deleteByMerging(50); // 刪除根節點（雙子樹）
        System.out.print("刪除 50 後："); bst.inOrder(); // 20 30 35 40 60 70 80
        bst.deleteByMerging(30); // 刪除單子樹節點
        System.out.print("刪除 30 後："); bst.inOrder(); // 20 35 40 60 70 80
    }

    // 簡易插入（測試用）
    public void insert(int key) {
        root = insertRec(root, key);
    }
    private Node insertRec(Node node, int key) {
        if (node == null) return new Node(key);
        if (key < node.key) node.left = insertRec(node.left, key);
        else if (key > node.key) node.right = insertRec(node.right, key);
        return node;
    }
}

圖解合併過程（刪除根節點 50）

        50                    刪除 50                    40
       /  \        --->      /  \        --->           /  \
     30    70               30   70       合併          30   70
    / \   / \              / \   / \                    \   / \
   20 40 60 80            20 40 60 80                   20 35 60 80
       \                                         (左子樹最大 40 接管右子樹 70)
       35

關鍵點總結

• 時間複雜度：O(h)，h 為樹高。平衡樹為 O(log n)，退化鏈表為 O(n)。
• 合併策略對稱性：同樣可用「右子樹最左節點（最小值）接管左子樹」，邏輯鏡像對稱。
• 替代方案：複製替換法：將前驅/後繼節點的鍵值複製給被刪節點，再遞迴刪除前驅/後繼節點（該節點至多有一個子樹，處理簡單）。兩種方法均正確，合併法較少一次遞迴調用。
• 生產建議：實務中推薦使用成熟庫（如 Java 內建 TreeMap、Guava、或資料庫索引），手寫 BST 僅供教學與面試準備。