如何有效地建立从平面结构的树？ [英] 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.

有没有循环引用。一个节点是的RootNode时PARENTID == null或PARENTID时，不能在其他对象中找到

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屋！