C# 遞歸構建樹形結構通用算法：數組轉樹函數完整實現

C# 遞歸構建樹形結構通用算法：數組轉樹函數完整實現

將扁平數組/列表轉換為樹形結構是前後端交互、權限菜單、組織架構、分類目錄等場景的高頻需求。本文提供一個**高性能、強類型、可配置深度限制**的 C# 通用樹構建函數，並解析核心邏輯與使用技巧。

一、完整代碼實現

using System;
using System.Collections.Generic;

public static class TreeHelper
{
    /// 

    /// 將扁平列表遞歸構建為樹形結構
    /// 
    /// 節點類型
    /// 扁平數據源 (List<T>)
    /// 父節點 ID (根節點傳 0 或 null)
    /// 主鍵屬性名 (預設 "id")
    /// 父鍵屬性名 (預設 "pid")
    /// 子節點集合屬性名 (預設 "child")
    /// 最大遞歸深度 (0=無限制，預防循環引用)
    /// 樹形結構根節點列表
    public static List GetTree(
        List data,
        object pid = null,
        string key = "id",
        string pKey = "pid",
        string childKey = "child",
        int maxDepth = 0) where T : class
    {
        int depth = 0;
        return BuildTreeRecursive(data, pid, key, pKey, childKey, maxDepth, ref depth);
    }

    private static List BuildTreeRecursive(
        List data,
        object pid,
        string key,
        string pKey,
        string childKey,
        int maxDepth,
        ref int depth) where T : class
    {
        depth++;
        
        // 深度保護：預設最大深度 = 數據量平方，防止無限遞歸
        if (maxDepth <= 0) maxDepth = data.Count * data.Count;
        if (depth > maxDepth)
        {
            throw new InvalidOperationException($"遞歸深度超過限制: {maxDepth}，疑似存在循環引用");
        }

        var tree = new List();
        var keyProp = typeof(T).GetProperty(key);
        var pKeyProp = typeof(T).GetProperty(pKey);
        var childProp = typeof(T).GetProperty(childKey);

        if (keyProp == null || pKeyProp == null || childProp == null)
        {
            throw new ArgumentException($"類型 {typeof(T).Name} 缺少必要屬性: {key}/{pKey}/{childKey}");
        }

        foreach (var item in data)
        {
            var itemPid = pKeyProp.GetValue(item);
            if (Equals(itemPid, pid))
            {
                // 遞歸構建子樹
                var children = BuildTreeRecursive(data, keyProp.GetValue(item), key, pKey, childKey, maxDepth, ref depth);
                if (children.Count > 0)
                {
                    childProp.SetValue(item, children);
                }
                tree.Add(item);
            }
        }

        depth--;
        return tree;
    }
}

二、核心設計亮點

三、實體類定義範例

public class MenuNode
{
    public int Id { get; set; }
    public int Pid { get; set; }
    public string Name { get; set; }
    public string Url { get; set; }
    public int Sort { get; set; }
    public List Child { get; set; } = new List();
}

四、調用示例

// 1. 準備扁平數據 (通常來自資料庫查詢)
var flatMenus = new List
{
    new MenuNode { Id = 1, Pid = 0, Name = "系統管理", Sort = 1 },
    new MenuNode { Id = 2, Pid = 0, Name = "業務管理", Sort = 2 },
    new MenuNode { Id = 3, Pid = 1, Name = "用戶管理", Sort = 1 },
    new MenuNode { Id = 4, Pid = 1, Name = "角色管理", Sort = 2 },
    new MenuNode { Id = 5, Pid = 3, Name = "用戶列表", Sort = 1 },
    new MenuNode { Id = 6, Pid = 3, Name = "新增用戶", Sort = 2 },
};

// 2. 構建樹
var treeMenus = TreeHelper.GetTree(flatMenus, pid: 0, key: "Id", pKey: "Pid", childKey: "Child");

// 3. 序列化輸出 (JSON)
var json = Newtonsoft.Json.JsonConvert.SerializeObject(treeMenus, Formatting.Indented);
Console.WriteLine(json);

五、效能優化建議 (大數據量場景)

遞歸 + 反射 + 線性查找 在 10 萬+ 節點時效能下降。優化方案：

1. 字典索引查找：預先建立 Dictionary<object, List<T>> pidToChildren，O(1) 定位子節點
2. 編譯表達式樹：替代反射獲取屬性值
3. 非遞歸棧實現：手動棧避免棧溢出
4. 並行構建：獨立分支可並行處理

優化版核心邏輯 (字典索引)

var lookup = data.GroupBy(x => pKeyProp.GetValue(x))
                 .ToDictionary(g => g.Key, g => g.ToList());

// 遞歸時直接 lookup[pid] 獲取子節點，無需遍歷全量 data

六、常見坑點與解決

七、前端配合 (Vue/React 渲染樹形組件)

<!-- Vue 3 + Element Plus 範例 -->
<el-tree :data="menuTree" 
         node-key="id" 
         :props="{ children: 'child', label: 'name' }" 
         show-checkbox 
         check-strictly 
         default-expand-all>
</el-tree>

總結

通用樹構建函數以**泛型 + 反射 + 可配置屬性名 + 深度保護**為核心設計，滿足 90% 以上業務場景。大數據量時引入字典索引優化查找，配合前端樹形組件即可完整實現「資料庫扁平存儲 → 後端構建樹 → 前端渲染交互」全鏈路閉環。