algorithm - 如何从平面结构高效地构建树？

Question

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

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

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

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

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

Answer 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);
}