小编典典

如何有效地从平面结构中构建树?

all

我有一堆扁平结构的物体。这些对象具有一个ID和一个ParentID属性,因此它们可以排列在树中。它们没有特定的顺序。每个ParentID属性不一定与ID结构中的
an 匹配。因此,它们可能是从这些物体中出现的几棵树。

您将如何处理这些对象以创建结果树?

我离解决方案不远,但我确信它远非最佳......

我需要创建这些树,然后以正确的顺序将数据插入数据库。

没有循环引用。当 ParentID == null 或在其他对象中找不到 ParentID 时,节点是 RootNode


阅读 147

收藏
2022-07-27

共1个答案

小编典典

将对象的 ID 存储在映射到特定对象的哈希表中。枚举所有对象并找到它们的父对象(如果存在)并相应地更新其父指针。

class MyObject
{ // The actual object
    public int ParentID { get; set; }
    public int ID { get; set; }
}

class Node
{
    public List<Node> Children = new List<Node>();
    public Node Parent { get; set; }
    public MyObject AssociatedObject { get; set; }
}

IEnumerable<Node> BuildTreeAndGetRoots(List<MyObject> actualObjects)
{
    Dictionary<int, Node> lookup = new Dictionary<int, Node>();
    actualObjects.ForEach(x => lookup.Add(x.ID, new Node { AssociatedObject = x }));
    foreach (var item in lookup.Values) {
        Node proposedParent;
        if (lookup.TryGetValue(item.AssociatedObject.ParentID, out proposedParent)) {
            item.Parent = proposedParent;
            proposedParent.Children.Add(item);
        }
    }
    return lookup.Values.Where(x => x.Parent == null);
}
2022-07-27