☰

平面構造から木を構築するにはどうすればいいですか? 質問する

tag-icon • tag-icon algorithm tree language-agnostic hierarchical-data
平面構造から木を構築するにはどうすればいいですか? 質問する

フラットな構造のオブジェクトが多数あります。これらのオブジェクトには および プロパティがありID、ParentIDツリーに配置できます。順序は特に決まっていません。

各ParentIDプロパティは、必ずしもID構造内の と一致するわけではありません。したがって、これらのオブジェクトから複数のツリーが出現する可能性があります。

これらのオブジェクトを処理して結果のツリーを作成するにはどうすればよいでしょうか?

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

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

ベストアンサー1

オブジェクトの ID を、特定のオブジェクトにマッピングするハッシュ テーブルに格納します。すべてのオブジェクトを列挙し、親が存在する場合はそれを見つけて、それに応じて親ポインタを更新します。

C# の場合:

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

おすすめ記事