從遞歸到極致優化：樹結構構建的性能演進之路

一次簡單的代碼優化，性能提升 超千倍！本文通過實測數據，揭示樹結構構建中隱藏的性能陷阱，並給出最佳實踐。

📖 前言

在日常開發中，我們經常需要處理樹形結構的數據：組織架構、菜單導航、商品分類、文件目錄……這些場景都需要將扁平的數據庫記錄轉換為層級樹結構。

今天，讓我們從最直觀的遞歸實現開始，一步步優化到極致性能，看看這條優化之路上都有哪些坑。

本文將回答：

• ✅ 構建樹的常見方式有哪些？
• ✅ 為什麼有些實現在大數據量下會崩潰？
• ✅ 如何用一行代碼實現數百倍性能提升？
• ✅ ILookup 為什麼這麼快？

測試環境：

• .NET 8.0
• 測試數據：10,000 ~ 100,000 個節點
• 硬件：普通筆記本電腦。11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz (2.42 GHz) | 16.0 GB

第一章：最直觀的實現 - 遞歸方式

1.1 數據模型

首先定義我們的節點結構：

// 扁平數據（數據庫記錄）
public class Node
{
    public int Id { get; set; }
    public int ParentId { get; set; }  // 0 表示根節點
    public string Name { get; set; }
}

// 樹結構
public class TreeItem<T>
{
    public T Node { get; set; }
    public List<TreeItem<T>> Children { get; set; } = new();
}

1.2 遞歸實現

最直觀的思路：對每個節點，遞歸查找它的子節點。

public static TreeItem<Node> BuildTreeRecursive(List<Node> nodes)
{
    var root = nodes.First(n => n.ParentId == 0);
    return BuildNode(nodes, root);
}

private static TreeItem<Node> BuildNode(List<Node> allNodes, Node current)
{
    var item = new TreeItem<Node> { Node = current };
    
    // 🔴 關鍵：查找當前節點的所有子節點
    var children = allNodes.Where(n => n.ParentId == current.Id).ToList();
    
    foreach (var child in children)
    {
        item.Children.Add(BuildNode(allNodes, child));
    }
    
    return item;
}

優點：

• ✅ 代碼簡潔、易理解
• ✅ 符合樹的自然定義
• ✅ 適合小規模數據（< 1,000 節點）

缺點：

• ❌ 性能問題：時間複雜度 O(n²)
• ❌ 棧溢出風險：深度 > 1,000 層會崩潰

讓我們先聊聊第二個問題。

第二章：遞歸的陷阱 - 棧溢出

2.1 問題重現

測試一個鏈表型樹（每個節點只有一個子節點，深度 = 節點數）：

// 生成 10,000 個節點的鏈表樹
var nodes = new List<Node>();
for (int i = 1; i <= 10000; i++)
{
    nodes.Add(new Node 
    { 
        Id = i, 
        ParentId = i - 1,  // 形成鏈表：0 → 1 → 2 → ... → 10000
        Name = $"Node_{i}" 
    });
}

var tree = BuildTreeRecursive(nodes);  // 💥 StackOverflowException!

結果：

System.StackOverflowException: Exception of type 'System.StackOverflowException' was thrown.

2.2 為什麼會棧溢出？

C# 中每次函數調用都會在調用棧上分配內存（存儲局部變量、返回地址等）。遞歸深度過大時，棧空間耗盡。

典型限制：

• Windows：~1,000 層遞歸（棧大小 1MB）
• Linux：~10,000 層（棧大小可調整）

2.3 解決方案一：深度保護

private const int MAX_DEPTH = 1000;

private static TreeItem<Node> BuildNode(List<Node> allNodes, Node current, int depth)
{
    if (depth > MAX_DEPTH)
        throw new InvalidOperationException("樹深度超過限制，建議使用迭代方式");
    
    var item = new TreeItem<Node> { Node = current };
    var children = allNodes.Where(n => n.ParentId == current.Id).ToList();
    
    foreach (var child in children)
    {
        item.Children.Add(BuildNode(allNodes, child, depth + 1));
    }
    
    return item;
}

這樣至少能提前發現問題，而不是讓程序直接崩潰。

第三章：迭代方式 - DFS 與 BFS

既然遞歸有深度限制，我們用迭代替代遞歸。

3.1 DFS（深度優先搜索）- 使用棧

public static TreeItem<Node> BuildTreeDFS(List<Node> nodes)
{
    var root = new TreeItem<Node> 
    { 
        Node = nodes.First(n => n.ParentId == 0) 
    };
    
    var stack = new Stack<TreeItem<Node>>();
    stack.Push(root);

    while (stack.Count > 0)
    {
        var current = stack.Pop();
        
        // 🔴 仍然是線性查找
        var children = nodes
            .Where(n => n.ParentId == current.Node.Id)
            .OrderByDescending(n => n.Id)
            .ToList();
        
        foreach (var child in children)
        {
            var childItem = new TreeItem<Node> { Node = child };
            current.Children.Add(childItem);
            stack.Push(childItem);
        }
    }

    return root;
}

3.2 BFS（廣度優先搜索）- 使用隊列

public static TreeItem<Node> BuildTreeBFS(List<Node> nodes)
{
    var root = new TreeItem<Node> 
    { 
        Node = nodes.First(n => n.ParentId == 0) 
    };
    
    var queue = new Queue<TreeItem<Node>>();
    queue.Enqueue(root);

    while (queue.Count > 0)
    {
        var current = queue.Dequeue();
        
        // 🔴 仍然是線性查找
        var children = nodes
            .Where(n => n.ParentId == current.Node.Id)
            .OrderBy(n => n.Id)
            .ToList();
        
        foreach (var child in children)
        {
            var childItem = new TreeItem<Node> { Node = child };
            current.Children.Add(childItem);
            queue.Enqueue(childItem);
        }
    }

    return root;
}

3.3 迭代 vs 遞歸

看起來問題解決了？並沒有！ 讓我們做個性能測試。

第四章：性能災難 - O(n²) 的真相

4.1 性能測試

為了貼合實際情況，我分了三個場景來進行測試：深層樹(層級很深，每層節點數量少)，超寬樹(層級很淺，但是每層節點數量多)，平衡樹(深度和寬度都相對平均，整體結構有點類似平衡二叉樹)。節點數量：10萬個(節點少了也看不出什麼效果)。
直接貼圖看結果（基於RELEASE模式編譯）：

核心算法代碼上面已經貼出，具體數據構建以及測試代碼，這裏就不貼出來了，如果有想看的朋友，可以留言。

🚨 注意：

• 10 萬節點用了 40-50秒！
• 遞歸方式早已棧溢出

4.2 性能分析：為什麼這麼慢？

讓我們看看這段代碼：

while (stack.Count > 0)  // 遍歷所有節點：n 次
{
    var current = stack.Pop();
    
    // 每次都要掃描整個列表！
    var children = nodes.Where(n => n.ParentId == current.Node.Id);  // O(n)
    // ...
}

時間複雜度分析：

• 外層循環：O(n) - 遍歷所有節點
• 內層 Where：O(n) - 每次掃描整個列表
• 總複雜度：O(n²)

具體計算：

• 50,000 個節點 → 需要 25 億次比較操作！
• 100,000 個節點 → 需要 100 億次比較操作！

這就是性能殺手！

4.3 核心問題

// 🔴 問題代碼：在循環中使用 Where
foreach (var node in nodes)  // n 次
{
    var children = allNodes.Where(n => n.ParentId == node.Id);  // 每次 O(n)
    // 總複雜度：O(n²)
}

這是實際項目中最常見的性能陷阱！

第五章：極致優化 - ILookup 的魔法

5.1 核心思路：空間換時間

既然每次都要查找 ParentId == xxx 的節點，為什麼不提前建立索引？

// 🔴 原來：每次查找都要掃描整個列表
var children = nodes.Where(n => n.ParentId == parentId);  // O(n)

// ✅ 現在：提前建立索引，查找變成 O(1)
var lookup = nodes.ToLookup(n => n.ParentId);  // 一次性建立索引 O(n)
var children = lookup[parentId];  // 直接查找 O(1)

5.2 什麼是 ILookup？

ILookup<TKey, TElement> 是 LINQ 提供的一個接口，類似於 Dictionary<TKey, List<TValue>>，但：

1. 一鍵多值：自動處理一對多關係
2. 不會拋異常：查詢不存在的鍵返回空集合
3. 基於哈希表：查找時間 O(1)
4. 只讀不可變：線程安全

語法：

// 創建
ILookup<int, Node> lookup = nodes.ToLookup(n => n.ParentId);

// 查詢（即使 999 不存在也不會異常）
IEnumerable<Node> children = lookup[999];  // 返回空集合

// 檢查是否存在
bool exists = lookup.Contains(999);

// 遍歷所有分組
foreach (var group in lookup)
{
    Console.WriteLine($"ParentId: {group.Key}, Count: {group.Count()}");
}

5.3 優化後的代碼

只需改一行！

public static TreeItem<Node> BuildTreeDFSOptimized(IEnumerable<Node> nodes)
{
    var nodeList = nodes.ToList();
    
    // ✅ 核心優化：提前建立索引
    var lookup = nodeList.ToLookup(n => n.ParentId);  // 👈 只加了這一行！
    
    var root = new TreeItem<Node> 
    { 
        Node = nodeList.First(n => n.ParentId == 0) 
    };
    
    var stack = new Stack<TreeItem<Node>>();
    stack.Push(root);

    while (stack.Count > 0)
    {
        var current = stack.Pop();
        
        // ✅ 從 O(n) 變成 O(1)
        var children = lookup[current.Node.Id]  // 👈 改這裏
            .OrderByDescending(n => n.Id)
            .ToList();
        
        foreach (var child in children)
        {
            var childItem = new TreeItem<Node> { Node = child };
            current.Children.Add(childItem);
            stack.Push(childItem);
        }
    }

    return root;
}

改動對比：

public static TreeItem<Node> BuildTreeDFS(List<Node> nodes)
{
+   var lookup = nodes.ToLookup(n => n.ParentId);
    // ...
    while (stack.Count > 0)
    {
        var current = stack.Pop();
-       var children = nodes.Where(n => n.ParentId == current.Node.Id);
+       var children = lookup[current.Node.Id];
    }
}

就這麼簡單！

第六章：性能對決 - 實測數據

6.1 完整測試

測試代碼：

internal class TreeBuilder
{
    private const int MAX_RECURSION_DEPTH = 1000; // 最大遞歸深度限制

    #region 1. 遞歸方式構建樹（原始 - 每次線性查找，帶深度保護）
    public static TreeItem<Node> BuildTreeRecursive(IEnumerable<Node> nodes)
    {
        var nodeList = nodes.ToList();
        var rootNode = nodeList.FirstOrDefault(n => n.ParentId == 0) ?? throw new InvalidOperationException("No root node found");
        
        return BuildRecursiveNode(nodeList, rootNode, 0);
    }

    private static TreeItem<Node> BuildRecursiveNode(List<Node> allNodes, Node currentNode, int depth)
    {
        // 深度保護：超過限制時拋出異常，避免真正的棧溢出
        if (depth > MAX_RECURSION_DEPTH)
        {
            throw new StackOverflowException($"遞歸深度超過限制 ({MAX_RECURSION_DEPTH})");
        }

        var treeItem = new TreeItem<Node> { Node = currentNode };
        
        // O(n) 線性查找子節點
        var children = allNodes.Where(n => n.ParentId == currentNode.Id).ToList();
        
        foreach (var child in children)
        {
            treeItem.Children.Add(BuildRecursiveNode(allNodes, child, depth + 1));
        }
        
        return treeItem;
    }
    #endregion

    #region 2. DFS方式構建樹（原始 - 使用棧，每次線性查找）
    public static TreeItem<Node> BuildTreeDFS(IEnumerable<Node> nodes)
    {
        var nodeList = nodes.ToList();
        var rootNode = nodeList.FirstOrDefault(n => n.ParentId == 0) ?? throw new InvalidOperationException("No root node found");
        
        var root = new TreeItem<Node> { Node = rootNode };
        var stack = new Stack<TreeItem<Node>>();
        stack.Push(root);

        while (stack.Count > 0)
        {
            var current = stack.Pop();
            
            // O(n) 線性查找子節點
            var children = nodeList.Where(n => n.ParentId == current.Node.Id).OrderByDescending(n => n.Id).ToList();
            
            foreach (var child in children)
            {
                var childItem = new TreeItem<Node> { Node = child };
                current.Children.Add(childItem);
                stack.Push(childItem);
            }
        }

        return root;
    }
    #endregion

    #region 3. BFS方式構建樹（原始 - 使用隊列，每次線性查找）
    public static TreeItem<Node> BuildTreeBFS(IEnumerable<Node> nodes)
    {
        var nodeList = nodes.ToList();
        var rootNode = nodeList.FirstOrDefault(n => n.ParentId == 0) ?? throw new InvalidOperationException("No root node found");
        
        var root = new TreeItem<Node> { Node = rootNode };
        var queue = new Queue<TreeItem<Node>>();
        queue.Enqueue(root);

        while (queue.Count > 0)
        {
            var current = queue.Dequeue();
            
            // O(n) 線性查找子節點
            var children = nodeList.Where(n => n.ParentId == current.Node.Id).OrderBy(n => n.Id).ToList();
            
            foreach (var child in children)
            {
                var childItem = new TreeItem<Node> { Node = child };
                current.Children.Add(childItem);
                queue.Enqueue(childItem);
            }
        }

        return root;
    }
    #endregion

    #region 4. 優化的遞歸方式（使用字典索引 - O(n)，帶深度保護）
    public static TreeItem<Node> BuildTreeRecursiveOptimized(IEnumerable<Node> nodes)
    {
        var nodeList = nodes.ToList();
        var lookup = nodeList.ToLookup(n => n.ParentId);
        
        var rootNode = nodeList.FirstOrDefault(n => n.ParentId == 0) ?? throw new InvalidOperationException("No root node found");
        
        return BuildRecursiveOptimizedNode(lookup, rootNode, 0);
    }

    private static TreeItem<Node> BuildRecursiveOptimizedNode(ILookup<int, Node> lookup, Node currentNode, int depth)
    {
        // 深度保護
        if (depth > MAX_RECURSION_DEPTH)
        {
            throw new StackOverflowException($"遞歸深度超過限制 ({MAX_RECURSION_DEPTH})");
        }

        var treeItem = new TreeItem<Node> { Node = currentNode };
        
        // O(1) 通過索引查找子節點
        var children = lookup[currentNode.Id];
        
        foreach (var child in children)
        {
            treeItem.Children.Add(BuildRecursiveOptimizedNode(lookup, child, depth + 1));
        }
        
        return treeItem;
    }
    #endregion

    #region 5. 優化的DFS（使用字典索引 - O(n)）
    public static TreeItem<Node> BuildTreeDFSOptimized(IEnumerable<Node> nodes)
    {
        var nodeList = nodes.ToList();
        var lookup = nodeList.ToLookup(n => n.ParentId);
        
        var rootNode = nodeList.FirstOrDefault(n => n.ParentId == 0) ?? throw new InvalidOperationException("No root node found");
        
        var root = new TreeItem<Node> { Node = rootNode };
        var stack = new Stack<TreeItem<Node>>();
        stack.Push(root);

        while (stack.Count > 0)
        {
            var current = stack.Pop();
            
            // O(1) 通過索引查找子節點
            var children = lookup[current.Node.Id].OrderByDescending(n => n.Id).ToList();
            
            foreach (var child in children)
            {
                var childItem = new TreeItem<Node> { Node = child };
                current.Children.Add(childItem);
                stack.Push(childItem);
            }
        }

        return root;
    }
    #endregion

    #region 6. 優化的BFS（使用字典索引 - O(n)）
    public static TreeItem<Node> BuildTreeBFSOptimized(IEnumerable<Node> nodes)
    {
        var nodeList = nodes.ToList();
        var lookup = nodeList.ToLookup(n => n.ParentId);
        
        var rootNode = nodeList.FirstOrDefault(n => n.ParentId == 0) ?? throw new InvalidOperationException("No root node found");
        
        var root = new TreeItem<Node> { Node = rootNode };
        var queue = new Queue<TreeItem<Node>>();
        queue.Enqueue(root);

        while (queue.Count > 0)
        {
            var current = queue.Dequeue();
            
            // O(1) 通過索引查找子節點
            var children = lookup[current.Node.Id].OrderBy(n => n.Id).ToList();
            
            foreach (var child in children)
            {
                var childItem = new TreeItem<Node> { Node = child };
                current.Children.Add(childItem);
                queue.Enqueue(childItem);
            }
        }

        return root;
    }
    #endregion        
}

6.2 測試結果

6.3 性能分析

時間複雜度對比：

內存佔用：

• 原始方式：O(n) - 只存儲節點
• 優化方式：O(n) - 節點 + Lookup 索引（額外約 20-30%）

為什麼集中算法的最終內存都是一樣的？
1.✅ 輸入數據相同：所有算法都使用同一個 nodes 列表（100,000 個 Node）
2.✅ 輸出結構相同：所有算法都構建相同的樹結構（TreeItem 對象）
3.✅ 最終內存相同：樹的總內存 = 節點數 × 每個 TreeItem 的大小

// 構建後的樹內存
100,000 個 TreeItem<Node> 對象
  ├─ 每個 TreeItem: ~80 字節
  │    ├─ Node 引用: 8 字節
  │    └─ Children List: 72 字節（包含數組、計數等）
  └─ 總計: ~7.8 MB

結論：

• ✅ 用 20-30% 內存換取 超過千倍的性能提升
• ✅ 絕對值得！

第七章：深入理解 ILookup

7.1 為什麼 ILookup 這麼快？

內部實現原理（簡化版）：

// ToLookup 內部大致做了這些事
public static ILookup<TKey, TElement> ToLookup<TKey, TElement>(
    this IEnumerable<TElement> source, 
    Func<TElement, TKey> keySelector)
{
    // 1. 創建哈希表
    var groups = new Dictionary<TKey, List<TElement>>();
    
    // 2. 遍歷一次，建立索引 - O(n)
    foreach (var item in source)
    {
        var key = keySelector(item);
        
        if (!groups.ContainsKey(key))
            groups[key] = new List<TElement>();
        
        groups[key].Add(item);
    }
    
    // 3. 返回只讀的 Lookup
    return new Lookup<TKey, TElement>(groups);
}

// 查找時 - O(1)
public IEnumerable<TElement> this[TKey key] 
{
    get 
    {
        return groups.ContainsKey(key) 
            ? groups[key] 
            : Enumerable.Empty<TElement>();  // 不存在返回空集合
    }
}

關鍵點：

1. 使用 Dictionary 作為底層存儲（哈希表）
2. 查找時間：O(1) - 直接通過哈希值定位
3. 不存在的鍵返回空集合，不拋異常

7.2 ILookup vs Dictionary vs GroupBy

var nodes = GetNodes();

// 1. GroupBy - 每次查詢都重新分組（慢！）
var groups = nodes.GroupBy(n => n.ParentId);
var children1 = groups.FirstOrDefault(g => g.Key == 100)?.ToList();  // O(n) 每次都分組

// 2. Dictionary - 需要手動處理一對多
var dict = new Dictionary<int, List<Node>>();
foreach (var node in nodes)
{
    if (!dict.ContainsKey(node.ParentId))
        dict[node.ParentId] = new List<Node>();
    dict[node.ParentId].Add(node);
}
var children2 = dict.ContainsKey(100) ? dict[100] : new List<Node>();  // O(1) 但需要判斷

// 3. Lookup - 一行搞定，自動處理一對多（快！）
var lookup = nodes.ToLookup(n => n.ParentId);
var children3 = lookup[100];  // O(1) 且不需要判斷

對比表：

第八章：實戰應用

8.1 常見場景

場景1：訂單-訂單項

// ❌ 慢
foreach (var order in orders)
{
    order.Items = orderItems.Where(oi => oi.OrderId == order.Id).ToList();  // O(n²)
}

// ✅ 快
var itemsLookup = orderItems.ToLookup(oi => oi.OrderId);
foreach (var order in orders)
{
    order.Items = itemsLookup[order.Id].ToList();  // O(n)
}

場景2：部門-員工

var empLookup = employees.ToLookup(e => e.DepartmentId);
foreach (var dept in departments)
{
    dept.Employees = empLookup[dept.Id].ToList();
}

場景3：分類-商品

var prodLookup = products.ToLookup(p => p.CategoryId);
foreach (var category in categories)
{
    category.Products = prodLookup[category.Id].ToList();
}

8.2 識別性能陷阱

搜索你的代碼庫，找這些模式：

// 🔍 危險信號
foreach + Where
for + FirstOrDefault
while + Any

// ✅ 優化建議
ToLookup + [key]
ToDictionary + [key]

CodeReview 清單：

• 循環中是否有 Where 查詢？
• 是否多次遍歷同一個集合？
• 數據量是否可能超過 1,000？
• 能否用 ToLookup 或 ToDictionary 優化？

第九章：完整對比 - 六種實現

9.1 所有實現方式

9.2 完整實現

六種實現方式的代碼上文已經給出，這裏不再重複了。

第十章：總結與最佳實踐

10.1 核心收穫

"優化查找，而非遍歷"

1. 性能陷阱： 循環中的 Where → O(n²)
2. 優化武器： ToLookup → O(n)
3. 一行改動： 性能提升數百倍
4. 遞歸限制： 深度 > 1000 層會棧溢出

10.2 最佳實踐

// ✅ 推薦寫法
var lookup = nodes.ToLookup(n => n.ParentId);
foreach (var node in nodes)
{
    var children = lookup[node.Id];
    // ...
}

// ❌ 避免寫法
foreach (var node in nodes)
{
    var children = allNodes.Where(n => n.ParentId == node.Id);  // O(n²)
}

10.3 何時使用 ILookup

10.4 記憶口訣

循環裏有 Where，性能就完蛋；
提前建 Lookup，速度飛上天！

📚 參考資料

• LINQ ToLookup 官方文檔
• 算法時間複雜度分析

一點題外話

DFS（Depth-First Search 深度優先搜索） 和BFS（Breadth-First Search 廣度優先搜索），這兩個術語都來自圖論，核心是搜索（在數據結構中尋找特定節點或路徑）。
但我們在構建樹時，只是按深度優先（或者廣度優先）的順序訪問節點並建立父子關係，並沒有“搜索”任何目標。嚴格來説，這應該叫深度優先遍歷（Depth-First Traversal）或深度優先構建（Depth-First Construction），廣度優先同理。
但為什麼大家都習慣叫DFS/BFS？
這是典型的算法術語泛化現象：

• 起源：圖論中的DFS確實是為了搜索/遍歷
• 發展：人們發現“用棧處理樹形結構”這種模式非常通用
• 泛化：任何使用棧來處理樹/圖結構的操作，都被口語化地稱為“用DFS的方式”
• 固化：面試、技術文章、開源代碼都這麼用，形成了約定俗成

類似例子還有很多：

• “用BFS爬取網頁” → 其實只是廣度優先遍歷URL
• “遞歸遍歷文件夾” → 並不是在搜索什麼
• “二叉樹的前/中/後序遍歷” → 其實也是DFS的特例，但很少人説“DFS二叉樹”

為什麼沒人糾正？

因為溝通成本高於精確性成本。當你面試時説“我用DFS把列表轉成樹”，所有人都秒懂。如果説“我用深度優先遍歷的迭代方式，藉助棧後進先出的特性來構建層級結構”——太囉嗦了，反而影響溝通效率。

但在實際開發中，“用DFS構建樹”已經是行業黑話，大家都接受這個語義泛化後的含義了。

🎯 結語

一次簡單的代碼優化，性能提升 超過千倍。

在實際項目中，這樣的優化機會比比皆是。關鍵是：

1. 測量：用 Stopwatch 測量，找到瓶頸
2. 分析：識別 O(n²) 的查找操作
3. 優化：用 ToLookup/ToDictionary 建立索引
4. 驗證：再次測量，確認提升

記住：

過早優化是萬惡之源，但該優化時別手軟！