如何从平面结构有效地构建一棵树? [英] How to efficiently build a tree from a flat structure?

问题描述

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

I have a bunch of objects in a flat structure. These objects have an ID and a ParentID property so they can be arranged in trees. They are in no particular order. Each ParentID property does not necessarily matches with an ID in the structure. Therefore their could be several trees emerging from these objects.

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

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

I'm not so far from a solution but I'm sure it is far from optimal...

我需要创建这些树，然后以正确的顺序将数据插入到数据库中.

I need to create these trees to then insert Data into a database, in proper order.

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

There are no circular references. A Node is a RootNode when ParentID == null or when ParentID can't be found in the other objects

推荐答案

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

Store IDs of the objects in a hash table mapping to the specific object. Enumerate through all the objects and find their parent if it exists and update its parent pointer accordingly.

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

这篇关于如何从平面结构有效地构建一棵树?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！