[解決済み] フラットな構造から効率的にツリーを構築する方法とは？

質問

フラット構造のオブジェクトがたくさんあります。これらのオブジェクトは ID と ParentID プロパティがあるので、ツリーに並べることができます。これらは順不同です。 それぞれ ParentID プロパティは、必ずしも ID を構造体の中に入れる。したがって、これらのオブジェクトから複数のツリーが出現する可能性があります。

これらのオブジェクトをどのように処理し、ツリーを作成するのでしょうか？

解決策には遠く及ばないが、最適には程遠いのでは......。

私は、これらのツリーを作成し、データベースにデータを挿入する必要があります、適切な順序で。

循環参照はありません。Nodeは、ParentID == nullのとき、またはParentIDが他のオブジェクトに見つからないとき、RootNodeになります。

解決方法は？

オブジェクトの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);
}