[Data Structure] 樹

樹 (Tree) 是一種非線性資料結構——資料以階層方式延伸，和陣列、鏈結串列、堆疊、佇列這類「一條線」的線性結構不同。最直覺的例子是公司組織圖：一個節點可以有多個子節點，但只有一個父節點。

術語

術語	英文	說明
節點	Node	樹中每一個資料單元
根節點	Root	樹的最頂端節點，整棵樹的起點
子節點	Child Node	某個節點直接連接的下層節點
父節點	Parent Node	某個節點直接連接的上層節點
葉節點	Leaf Node	沒有子節點的節點
邊	Edge	連接兩個節點的線
深度	Depth	某節點距離根節點的邊數，根節點的深度為 0
高度	Height	某節點到其最遠葉節點的邊數，整棵樹的高度即為根節點的高度
子樹	Subtree	某個節點與其所有後代節點所組成的樹

「深度」與「高度」很容易搞混：

深度 (Depth)：從上往下算，距離根節點多遠。
高度 (Height)：從下往上算，距離最遠的葉節點有多遠。

根節點的深度是 0，葉節點的高度也是 0，整棵樹的高度就等於根節點的高度。

二元樹 (Binary Tree)

最常見的樹類型。每個節點最多兩個子節點：左子節點 (Left Child) 與右子節點 (Right Child)。

二元樹的細分類型：以下四張圖並排展示四種形狀，差別在於「子節點有沒有填滿」「最後一層怎麼排」。

Full Binary Tree

每個節點恰好有 0 或 2 個子節點

Complete Binary Tree

除最後一層外每層填滿，最後一層靠左排列

Perfect Binary Tree

每一層完全填滿，所有葉節點在同一層

Balanced Binary Tree

任意節點左右子樹的高度差不超過 1

類型	說明
完整二元樹 (Full Binary Tree)	每個節點要麼沒有子節點，要麼就有恰好兩個子節點
完全二元樹 (Complete Binary Tree)	除了最後一層，每層都填滿；最後一層的節點盡量靠左排列
完美二元樹 (Perfect Binary Tree)	每一層都完全填滿，葉節點全部在同一層
平衡二元樹 (Balanced Binary Tree)	任意節點的左右子樹高度差不超過 1

二元搜尋樹 (BST)

二元樹的特殊形式，核心規則：

左子樹的所有節點值 < 根節點值 < 右子樹的所有節點值

搜尋邏輯：每次比較當前節點，目標比節點小則往左，比節點大則往右。每次比較排除一半範圍，類似二分搜尋。

節點結構

每個節點（TreeNode）裝一個值 value，加上兩個指向子節點的指標 left、right。

Java 節點類別

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
    }
}

插入與搜尋

插入：從根節點開始，新值比當前節點小就往左走、大就往右走，碰到 null 就把新節點掛在那裡。搜尋：同樣邏輯，碰到等值回傳命中，碰到 null 回傳找不到。

以空樹依序 insert [5, 3, 7, 1, 4, 6, 8]，每輪走訪路徑如下：

插入	走訪比較（新值 vs 節點值 → 方向）	新節點落在
5	空樹	成為根
3	3 `<` 5 → 左	5 的左子
7	7 `>` 5 → 右	5 的右子
1	1 `<` 5 → 左到 3；1 `<` 3 → 左	3 的左子
4	4 `<` 5 → 左到 3；4 `>` 3 → 右	3 的右子
6	6 `>` 5 → 右到 7；6 `<` 7 → 左	7 的左子
8	8 `>` 5 → 右到 7；8 `>` 7 → 右	7 的右子

最終樹長這樣：

搜尋示範：

搜尋 4：從 5 → 4 < 5 走左 → 3 → 4 > 3 走右 → 4 命中 ✅
搜尋 9：從 5 → 9 > 5 走右 → 7 → 9 > 7 走右 → 碰到 null，不存在 ❌

Java 實作（insert + search + inorder 驗證）

public class BST {
    public static void main(String[] args) {
        TreeNode root = null;
        int[] values = {5, 3, 7, 1, 4, 6, 8};

        for (int v : values) {
            root = insert(root, v);
        }

        // 中序走訪 BST 會輸出排序後的結果
        System.out.print("Inorder: ");
        inorder(root); // 輸出：1 3 4 5 6 7 8
        System.out.println();

        System.out.println(search(root, 4)); // true
        System.out.println(search(root, 9)); // false
    }

    static TreeNode insert(TreeNode node, int value) {
        if (node == null) return new TreeNode(value);
        if (value < node.value) node.left = insert(node.left, value);
        else if (value > node.value) node.right = insert(node.right, value);
        return node;
    }

    static boolean search(TreeNode node, int value) {
        if (node == null) return false;
        if (node.value == value) return true;
        if (value < node.value) return search(node.left, value);
        return search(node.right, value);
    }

    static void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        System.out.print(node.value + " ");
        inorder(node.right);
    }
}

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
    }
}

樹的走訪 (Traversal)

走訪是指依照某種順序拜訪樹中的每一個節點。常見的走訪方式分為兩大類：深度優先 (DFS) 與廣度優先 (BFS)。以下互動圖解以同一棵 BST 示範四種走訪順序，點按鈕切換模式，動畫會逐一標記節點被拜訪的先後：

深度優先搜尋 (DFS, Depth-First Search)

「先走到底，再回頭」。在樹上有三種變形，差別在於何時處理根節點：

走訪方式	順序	用途
前序走訪 (Preorder)	根 → 左 → 右	複製樹結構、序列化
中序走訪 (Inorder)	左 → 根 → 右	BST 中序走訪可輸出排序結果
後序走訪 (Postorder)	左 → 右 → 根	刪除樹、計算子樹大小

廣度優先搜尋 (BFS, Breadth-First Search)

又稱層序走訪 (Level-order Traversal)——先把同一層全部拜訪完，再進到下一層。使用佇列 (Queue) 實作：把根丟進 queue，不斷 pop 出來、印值、再把它的左右子（若存在）放進 queue，直到 queue 空。

Java 實作（四種走訪）

import java.util.LinkedList;
import java.util.Queue;

public class TreeTraversal {
    public static void main(String[] args) {
        TreeNode root = null;
        int[] values = {5, 3, 7, 1, 4, 6, 8};

        for (int v : values) {
            root = insert(root, v);
        }

        System.out.print("Preorder:  ");
        preorder(root);
        System.out.println();

        System.out.print("Inorder:   ");
        inorder(root);
        System.out.println();

        System.out.print("Postorder: ");
        postorder(root);
        System.out.println();

        System.out.print("BFS:       ");
        bfs(root);
        System.out.println();
    }

    static TreeNode insert(TreeNode node, int value) {
        if (node == null) return new TreeNode(value);
        if (value < node.value) node.left = insert(node.left, value);
        else if (value > node.value) node.right = insert(node.right, value);
        return node;
    }

    // 前序：根 → 左 → 右
    static void preorder(TreeNode node) {
        if (node == null) return;
        System.out.print(node.value + " ");
        preorder(node.left);
        preorder(node.right);
    }

    // 中序：左 → 根 → 右
    static void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        System.out.print(node.value + " ");
        inorder(node.right);
    }

    // 後序：左 → 右 → 根
    static void postorder(TreeNode node) {
        if (node == null) return;
        postorder(node.left);
        postorder(node.right);
        System.out.print(node.value + " ");
    }

    // BFS：逐層走訪
    static void bfs(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.value + " ");
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
}

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
    }
}

以上述範例（插入順序 5, 3, 7, 1, 4, 6, 8）為例，各走訪的輸出結果為：

走訪方式	輸出結果	說明
Preorder	`5 3 1 4 7 6 8`	根節點 5 最先輸出
Inorder	`1 3 4 5 6 7 8`	BST 中序走訪即為排序結果
Postorder	`1 4 3 6 8 7 5`	根節點 5 最後輸出
BFS	`5 3 7 1 4 6 8`	由上到下逐層輸出

BST 的時間複雜度

BST 的效能完全取決於樹的高度 $h$ （從根到最深葉節點的邊數）。若樹保持平衡， $h$ 約為 $\log_2 n$ （ $n$ 是節點總數）：

操作	平均情況	最差情況
搜尋	$O(\log n)$	$O(n)$
插入	$O(\log n)$	$O(n)$
刪除	$O(\log n)$	$O(n)$

最差情況 $O(n)$ 發生在樹退化為「斜樹」的時候。例如依序插入 1, 2, 3, 4, 5，每個新節點都比前一個大，就會形成一條向右傾斜的直線，樹的高度等於 $n$ ，搜尋效能退化為等同鏈結串列的 $O(n)$ 。

為了避免這種情況，實務上會採用自平衡樹（如 AVL Tree 或 Red-Black Tree），在插入或刪除後自動調整結構，維持 $O(\log n)$ 的效能。Java 的 TreeMap 底層就是用 Red-Black Tree 實作的。

BST 刪除

刪除要分 3 種情況處理，重點在於刪掉後還要維持「左 < 根 < 右」：

葉節點（沒有子）：直接拔掉
只有一個子：把唯一的子提上來取代被刪節點
有兩個子：找個「合法繼任者」來頂替——通常選中序後繼（右子樹裡的最小值）或中序前驅（左子樹裡的最大值），把繼任者的值複製到被刪節點，再把繼任者本身的位置遞迴刪掉（繼任者最多只有一個子，回到情況 1 或 2）

範例：對前面的樹（根 5、左子樹 1-3-4、右子樹 6-7-8）刪除根 5：

找右子樹最小值 = 6（中序後繼）
把 6 複製到根：樹變成 6 / 3, 7 / 1, 4, 6, 8
原本的葉節點 6 需要移除（情況 1），最終：6 / 3, 7 / 1, 4, -, 8

常見考法

#	題型	重點
1	給序列依序 insert 畫 BST	空樹起，逐一比對根走左右
2	寫出 preorder / inorder / postorder / level-order	3 個 DFS 差在根何時輸出；level-order 用 queue
3	BST 中序 = 排序序列	這是 BST 最重要性質
4	由走訪序列還原樹	preorder + inorder、或 postorder + inorder 可唯一還原；單一走訪不行
5	BST 刪除 3 種情況	葉、單子、雙子（用後繼 / 前驅）
6	BST 退化成斜樹	已排序序列 insert → 樹高 = $n$ → 搜尋 $O(n)$
7	完整/完全/完美/平衡二元樹辨析	完整（0 或 2 子）、完全（最後一層靠左）、完美（全滿）、平衡（高差 $\le 1$ ）
8	高度 vs 深度	深度由根往下、高度由葉往上
9	$n$ 節點二元樹的葉節點數	完美 BT： $\lceil n/2 \rceil$ ；完整 BT：degree-2 節點數 + 1
10	BST 搜尋複雜度推導	平衡 $h = \log_2 n$ 、斜樹 $h = n$

複雜度推導

平衡 BST $O(\log n)$ ： $n$ 節點的完美二元樹高度 $h = \lfloor \log_2 n \rfloor$ ；每層比較 $O(1)$
斜樹 $O(n)$ ： $h = n - 1$ ；退化成鏈結串列
Traversal $O(n)$ ：每節點恰訪一次（DFS 或 BFS 同）
AVL / Red-Black：保證 $h = O(\log n)$ ：RB tree 最差 $h \le 2 \log_2(n+1)$

考試常踩的陷阱

Preorder + Postorder 不能唯一還原：必須有 inorder 才行
BST 的 inorder 一定是排序：反過來：若 inorder 不遞增 → 不是 BST
刪除雙子節點不能直接砍：要用後繼（右子樹最小）或前驅（左子樹最大）替代
完整 ≠ 完全 ≠ 完美：三個詞在考試常被混用
BST 最差 $O(n)$ 不是 $O(\log n)$ ：平均才是 $O(\log n)$
BFS 用 queue、DFS 用 stack（或遞迴）：搞反會錯