C# 2.0 新特性深度解析（六）：遞迴迭代器在二叉樹上的完整實作

二叉樹資料結構定義

class Node
{
    public Node LeftNode;
    public Node RightNode;
    public T Item;
}

public class BinaryTree
{
    Node _root;
    public void Add(params T[] items) { foreach (var i in items) Add(i); }
    public void Add(T item) { /* 標準 BST 插入邏輯 */ }
}

中序遍歷迭代器實作

public IEnumerable InOrder
{
    get { return ScanInOrder(_root); }
}

IEnumerable ScanInOrder(Node root)
{
    if (root.LeftNode != null)
    {
        foreach (T item in ScanInOrder(root.LeftNode))
            yield return item;
    }
    yield return root.Item;
    if (root.RightNode != null)
    {
        foreach (T item in ScanInOrder(root.RightNode))
            yield return item;
    }
}

使用範例

var tree = new BinaryTree();
tree.Add(4, 6, 2, 7, 5, 3, 1);
foreach (int num in tree.InOrder)
    Trace.WriteLine(num); // 輸出 1,2,3,4,5,6,7

前序/後序遍歷擴展

同理新增 `PreOrder`、`PostOrder` 屬性，調整 `yield return` 位置：

• 前序：`yield return root.Item` → 左 → 右
• 後序：左 → 右 → `yield return root.Item`

遞迴迭代器效能深度分析

• 每個節點對應一個迭代器實例（編譯器生成狀態機類別）。
• 深度 n 樹：約 n 個迭代器實例，同時存活 ~log n。
• 大量 Gen 0 物件觸發頻繁 GC，深度 > 10⁴ 時明顯拖慢。
• 生產環境深層樹建議：手寫堆疊迭代（`Stack>`）避免分配。