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

Question

我有一个层次结构中的项目列表,我正在尝试将此列表解析为实际的对象层次结构.我正在使用修改的预订树遍历来存储/遍历此列表,因此我所拥有的是树的子集,包括所有子节点,按其"左"值排序.

例如,给定树:

• 项目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

我不知道如何做到这一点 - 跟踪父母,并能够处理更大的跳跃(例如,项目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();
}