C# 擴展方法進階實戰：通用樹結構遍歷器

前言

樹結構遍歷是常見需求 (組織架構、檔案系統、UI 控制項樹、AST)。本文實作通用的 GetDescendants 擴展方法，支援深度優先遍歷、泛型節點型別、過濾條件，並解決「根與子節點型別不同」 (如 TreeView/TreeNode) 的實際問題。

基礎版：同型別節點樹

public static IEnumerable<T> GetDescendants<T>(
    this T root,
    Func<T, IEnumerable<T>> childSelector,
    Predicate<T> filter = null)
{
    foreach (var child in childSelector(root))
    {
        if (filter == null || filter(child))
            yield return child;

        foreach (var descendant in child.GetDescendants(childSelector, filter))
            yield return descendant;
    }
}

應用範例：People 家族樹

public abstract class People
{
    public bool IsMale { get; set; }
    public abstract IEnumerable<People> Children { get; }
}

// 使用
var allDescendants = person.GetDescendants(p => p.Children);
var maleDescendants = person.GetDescendants(p => p.Children, p => p.IsMale);

進階版：根與子節點型別不同 (TreeView 場景)

public static IEnumerable<T> GetDescendants<TRoot, T>(
    this TRoot root,
    Func<TRoot, IEnumerable<T>> rootChildSelector,
    Func<T, IEnumerable<T>> childSelector,
    Predicate<T> filter = null)
{
    foreach (var child in rootChildSelector(root))
    {
        if (filter == null || filter(child))
            yield return child;

        foreach (var descendant in child.GetDescendants(childSelector, filter))
            yield return descendant;
    }
}

應用範例

// WinForms 控制項樹
var allControls = this.GetDescendants(c => c.Controls.Cast<Control>());
var checkedBoxes = this.GetDescendants(
    c => c.Controls.Cast<Control>(),
    c => (c is CheckBox) && ((CheckBox)c).Checked)
    .Cast<CheckBox>();

// TreeView 節點樹
var wineNodes = treeView1.GetDescendants(
    tv => tv.Nodes.Cast<TreeNode>(),
    tn => tn.Nodes.Cast<TreeNode>(),
    tn => tn.Text.EndsWith("酒"));

廣度優先遍歷 (BFS) 實作

public static IEnumerable<T> GetDescendantsBfs<T>(
    this T root,
    Func<T, IEnumerable<T>> childSelector,
    Predicate<T> filter = null)
{
    var queue = new Queue<T>(childSelector(root));
    while (queue.Count > 0)
    {
        var current = queue.Dequeue();
        if (filter == null || filter(current))
            yield return current;

        foreach (var child in childSelector(current))
            queue.Enqueue(child);
    }
}

效能與記憶體考量

• 遞迴深度：DFS 遞迴版可能堆疊溢位，極深樹請用 BFS 或显式堆疊版本。
• 延遲執行：yield return 提供串流式處理，避免一次載入所有節點。
• 重複遍歷：若樹結構有共享子節點 (DAG)，需加入 HashSet<T> 追蹤已訪問節點。

結語

通用樹遍歷器將「如何遍歷」與「做什麼處理」分離，配合 LINQ 可表達極具可讀性的樹查詢邏輯。建議將此類工具方法收納於專案共用函式庫，提升開發效率。