C# 與資料結構：二叉樹的遍歷演算法完整解析

二叉樹的儲存結構

二叉樹在記憶體中的儲存方式主要分為兩大類：循序儲存結構與鏈式儲存結構。選擇哪種方式，取決於樹的形態與操作需求。

1. 循序儲存結構（陣列實作）

此法將滿二叉樹由上至下、由左至右編號，依序存入陣列。若節點在陣列中的索引為 i，則具備以下數學性質：

• 若 i = 0，該節點為根節點，無雙親。
• 若 i > 0，其雙親索引為 (i - 1) / 2（整數除法）。
• 左子節點索引：2i + 1；右子節點索引：2i + 2。
• 若 i > 0 且為奇數，則為左孩子，兄弟索引為 i + 1；若為偶數，則為右孩子，兄弟索引為 i - 1。
• 深度為 k 的滿二叉樹需長度為 2^k - 1 的陣列。

此結構極適合完全二叉樹或滿二叉樹，可 O(1) 計算親屬關係，空間效率最高。但對於一般二叉樹，需以特殊值（如 null 或 #）佔位空節點，若樹稀疏（如退化為鏈表），空間浪費極大（深度 k 需 2^k - 1 空間），此時應改用鏈式結構。

2. 鏈式儲存結構

鏈式結構以節點物件加指標連結，彈性大、不浪費空間，是二叉樹最常用的儲存方式。

• 二叉鏈表：每節點含資料、左指標 left、右指標 right。
• 三叉鏈表：在二叉鏈表基礎上增加指向雙親的 parent 指標，便於向上查找。
• 雙親鏈表：僅儲存雙親索引與左右標識，物理上為循序結構，需輔助陣列遍歷，適合頻繁查找雙親、較少遍歷全樹的場景。

後續演算法均以二叉鏈表為基礎。

二叉樹的遍歷

遍歷是指依特定順序訪問樹中每個節點一次且僅一次。本質是將非線性結構線性化，為各種樹操作奠基。

深度優先遍歷（DFS）

依遞歸定義：樹 = 根節點(D) + 左子樹(L) + 右子樹(R)。先左後右有三種經典順序：

以圖例樹為例：

• 先序：A B D E C F
• 中序：D B E A C F
• 後序：D E B F C A

C# 遞歸實作

public class Node {
    public object Data { get; private set; }
    public Node Left { get; set; }
    public Node Right { get; set; }
    public Node(object data) { Data = data; }
    public override string ToString() => Data.ToString();
}

public class BinaryTree {
    private Node _head;
    // 建構函式略（依字串 "ABCDE#F" 建樹，# 表空節點）

    // 先序遍歷
    public void PreOrder(Node node) {
        if (node != null) {
            Console.Write(node);
            PreOrder(node.Left);
            PreOrder(node.Right);
        }
    }
    // 中序遍歷
    public void MidOrder(Node node) {
        if (node != null) {
            MidOrder(node.Left);
            Console.Write(node);
            MidOrder(node.Right);
        }
    }
    // 後序遍歷
    public void AfterOrder(Node node) {
        if (node != null) {
            AfterOrder(node.Left);
            AfterOrder(node.Right);
            Console.Write(node);
        }
    }
}

廣度優先遍歷（BFS / 層序遍歷）

從根節點開始，逐層由左至右訪問。需借助佇列實作，不使用遞歸。

1. 根節點入佇列。
2. 佇列不空時：出佇列取節點 D，訪問之。
3. 若 D 有左子節點，入佇列；同理處理右子節點。
4. 重複步驟 2-3 直到佇列為空。

圖例樹層序結果：A B C D E F

C# 佇列實作

public void LevelOrder() {
    Queue queue = new Queue();
    queue.Enqueue(_head);
    while (queue.Count > 0) {
        Node node = (Node)queue.Dequeue();
        Console.Write(node);
        if (node.Left != null) queue.Enqueue(node.Left);
        if (node.Right != null) queue.Enqueue(node.Right);
    }
}

總結

• 循序儲存適合完全二叉樹，查找親屬 O(1)；鏈式儲存通用、節省空間。
• DFS 三序（先/中/後序）以遞歸實作最直觀，對應「訪問根節點」的時機不同。
• BFS 層序需佇列輔助，適用於逐層處理、求最短路徑等場景。
• 掌握遍歷是解決樹相關問題（如序列化、重建、路徑查找）的基石。