.net - 从父/子的平面列表构建层次结构对象

Question

我有一个层次结构中的项目列表，我正在尝试将此列表解析为实际的对象层次结构。我正在使用modified pre-order tree traversal存储/迭代此列表，所以我拥有的是树的子集，包括所有子项，按其“左”值排序。

例如，给定树:

• 项目A
  • 项目 A.1
  • 项目 A.2
    • 项目 A.2.2
• 项目B
  • 项目 B.1
• 项目C

我得到了列表:

• 项目 A、项目 A.1、项目 A.2、项目 A.2.2、项目 B、项目 B.1、项目 C

(这是按照修改后的预排序树设置中的“左”值的顺序)。

我想要做的是将其解析为包含树实际结构的对象，例如:

Class TreeObject {
    String Name;
    Guid ID; 
    Guid ParentID;
    List<TreeObject> Children;
}

平面列表作为 TreeObjects 列表返回 - 每个 TreeObject 都有 ID、ParentID、Left 和 Right 属性。我正在寻找的是一个函数:

List<TreeObject> FlatToHeirarchy(List<TreeObject> list); 

它接受平面列表，并返回一个嵌套列表。

换句话说:

List<TreeObject> flatSet = LoadTreeObjectsFromDatabase(); 
// flatSet.count == 7; flatSet(0).Children == null
List<TreeObject> nestedSet = FlatToHeirarchy(flatSet);
// nestedSet.count == 3; nestedSet(0).Children.count == 2

我不知道如何做到这一点 - 跟踪 parent ，并能够处理更大的跳跃(例如，项目 A.2.2 -> 项目 B)。

<小时/>

编辑:我正在寻找一种非暴力解决方案(例如，不循环多次，将项目移动到子节点中，直到只剩下顶级父节点)。我猜有一种优雅的方法可以循环一次，然后根据需要放置项目。

请记住，它们始终按层次结构顺序排列(因为我使用的是 MPTT)，因此给定的项目将始终是前一个项目的子项目或同级项目，或者至少与前一个项目共享父项目。它永远不会出现在树中的其他地方。

Answer 1

这是我最终编写的函数。我使用 MPTT 来存储对象，因此列表按“左”值的顺序排列，这基本上意味着父级始终位于列表中任何给定项目之前。换句话说，item.ParentID 引用的项始终已被添加(顶级或根节点的情况除外)。

public class TreeObject
{
    public int Id { get; set; }
    public int ParentId { get; set; }
    public string Name { get; set; }
    public IList<TreeObject> Children { get; set; } = new List<TreeObject>();
}

public IEnumerable<TreeObject> FlatToHierarchy(List<TreeObject> list)
{
    // hashtable lookup that allows us to grab references to containers based on id
    var lookup = new Dictionary<int, TreeObject>();
    // actual nested collection to return
    var nested = new List<TreeObject>();

    foreach (TreeObject item in list)
    {
        if (lookup.ContainsKey(item.ParentId))
        {
            // add to the parent's child list 
            lookup[item.ParentId].Children.Add(item);
        }
        else
        {
            // no parent added yet (or this is the first time)
            nested.Add(item);
        }
        lookup.Add(item.Id, item);
    }

    return nested;
}

和一个简单的测试(适用于 LinqPad):

void Main()
{
    var list = new List<TreeObject>() {
        new TreeObject() { Id = 1, ParentId = 0, Name = "A" },
        new TreeObject() { Id = 2, ParentId = 1, Name = "A.1" },
        new TreeObject() { Id = 3, ParentId = 1, Name = "A.2" },
        new TreeObject() { Id = 4, ParentId = 3, Name = "A.2.i" },
        new TreeObject() { Id = 5, ParentId = 3, Name = "A.2.ii" }
    };

    FlatToHierarchy(list).Dump();
}

结果:

由于我在 5 年后更新此内容，因此这里有一个递归 LINQ 版本:

public IList<TreeObject> FlatToHierarchy(IEnumerable<TreeObject> list, int parentId = 0) {
    return (from i in list 
            where i.ParentId == parentId 
            select new TreeObject {
                Id = i.Id, 
                ParentId = i.ParentId,
                Name = i.Name,
                Children = FlatToHierarchy(list, i.Id)
            }).ToList();
}