如何将C#中Tree类扁平列表转换为层级Directory类根对象？

这是处理扁平数据转层级结构的经典场景，最优方案是借助字典实现快速节点查找，把整体时间复杂度控制在O(n)级别，远优于递归查找父节点的O(n²)方案。下面是完整的实现思路和代码：

步骤1：定义目标层级类 #

首先我们需要定义最终的Directory类，包含名称和子节点列表：

public class Directory
{
    public string Name { get; set; }
    public List<Directory> Children { get; set; } = new List<Directory>();
}

步骤2：实现转换方法 #

核心思路是先把所有节点存入字典做缓存，再一次性完成父子关联：

public Directory ConvertFlatTreeToHierarchy(List<Tree> flatTreeData)
{
    // 字典用于快速通过Name查找对应的Directory实例
    var directoryLookup = new Dictionary<string, Directory>();
    Directory rootDirectory = null;

    // 第一遍遍历：创建所有Directory实例并缓存
    foreach (var treeEntry in flatTreeData)
    {
        var dir = new Directory { Name = treeEntry.Name };
        directoryLookup[treeEntry.Name] = dir;

        // 记录唯一的根节点（Parent为null的项）
        if (treeEntry.Parent == null)
        {
            rootDirectory = dir;
        }
    }

    // 第二遍遍历：将每个节点挂载到对应的父节点下
    foreach (var treeEntry in flatTreeData)
    {
        if (!string.IsNullOrEmpty(treeEntry.Parent) 
            && directoryLookup.TryGetValue(treeEntry.Parent, out var parentDir))
        {
            parentDir.Children.Add(directoryLookup[treeEntry.Name]);
        }
    }

    return rootDirectory;
}

为什么这是最优方案？ #

• 时间效率拉满：两次线性遍历，所有字典操作都是O(1)的时间复杂度，整体耗时和数据量成正比，大数据量下优势极其明显。
• 空间开销合理：用字典存储所有节点，空间复杂度O(n)，这是为了高效查找必须的开销，完全在可接受范围内。
• 鲁棒性强：通过TryGetValue处理了可能存在的无效父节点（比如数据里有不存在的Parent值），避免程序崩溃。

示例数据转换结果 #

针对你给出的示例数据，转换后的根节点结构如下：

• Name: "C:"
  • Children:
    • Name: "System"
      • Children:
        • Name: "Win"
    • Name: "Prog"

内容的提问来源于stack exchange，提问作者Alexandre