親子関係を再帰的にチェックしてツリー型リストを作成するC＃

Question

ツリー構造で表すことができるように、自身のリストを持つ1つのクラスがあります。

私はこれらのクラスのフラットなリストを引っ張り、それを平坦化したいと思います。

public class Group 
{ 
    public int ID {get;set;} 

    public int? ParentID {get;set;} 

    public List<Group> Children {get;set;} 

} 

私は、次の

List<Group> flatList = GetFlatList() //I CAN ALREADY DO THIS 
List<Group> tree = BuildTree(flatList); 

その波平明白な場合には、その親グループのIDプロパティに関連のParentIDを行うことができるようにしたいです。

EDIT

私はリストではなく単一のオブジェクトを返す午前理由として、いくつかの混乱があります。

私はアイテムのリストを持つUI要素を構築していますが、それぞれになぜ子があるのですか。したがって、初期リストにはルートノードはありません。これまでのソリューションのすべてがうまくいかないようです。

これは、Groupクラスを使用するツリー型構造のリストが本質的に必要であることを意味します。ここで

Answer 1

私はあなたのBuildTreeメソッドの戻りList<Group>する理由は考えていません - ツリーはルートノードを持っている必要がありますが、リストではなく、単一のGroup要素を返すと期待する必要があります。

私はIEnumerable<Group>に拡張メソッドを作成します。

public static class GroupEnumerable 
{ 
    public static IList<Group> BuildTree(this IEnumerable<Group> source) 
    { 
     var groups = source.GroupBy(i => i.ParentID); 

     var roots = groups.FirstOrDefault(g => g.Key.HasValue == false).ToList(); 

     if (roots.Count > 0) 
     { 
      var dict = groups.Where(g => g.Key.HasValue).ToDictionary(g => g.Key.Value, g => g.ToList()); 
      for (int i = 0; i < roots.Count; i++) 
       AddChildren(roots[i], dict); 
     } 

     return roots; 
    } 

    private static void AddChildren(Group node, IDictionary<int, List<Group>> source) 
    { 
     if (source.ContainsKey(node.ID)) 
     { 
      node.Children = source[node.ID]; 
      for (int i = 0; i < node.Children.Count; i++) 
       AddChildren(node.Children[i], source); 
     } 
     else 
     { 
      node.Children = new List<Group>(); 
     } 
    } 
} 

使用

var flatList = new List<Group>() { 
    new Group() { ID = 1, ParentID = null }, // root node 
    new Group() { ID = 2, ParentID = 1 }, 
    new Group() { ID = 3, ParentID = 1 }, 
    new Group() { ID = 4, ParentID = 3 }, 
    new Group() { ID = 5, ParentID = 4 }, 
    new Group() { ID = 6, ParentID = 4 } 
}; 


var tree = flatList.BuildTree(); 

Answer 2

を使用すると、1つの行でこれを行うことができます方法は次のとおりです。最後にあなたは親がnullであるノードを取得したい場合は

BuildTree(flatList); 

：

static void BuildTree(List<Group> items) 
{ 
    items.ForEach(i => i.Children = items.Where(ch => ch.ParentID == i.ID).ToList()); 
} 

あなたはこのようにそれを呼び出すことができます（つまり、最上位のノード）であれば、これを簡単に行うことができます：

static List<Group> BuildTree(List<Group> items) 
{ 
    items.ForEach(i => i.Children = items.Where(ch => ch.ParentID == i.ID).ToList()); 
    return items.Where(i => i.ParentID == null).ToList(); 
} 

そして拡張メソッドにしたいのですがちょうどメソッドのシグネチャでthisを追加します。

static List<Group> BuildTree(this List<Group> items) 

その後、あなたはこのようにそれを呼び出すことができます。

var roots = flatList.BuildTree(); 

Answer 3

を私は解決策は、彼らがO（N^2）について私たちを与えることが示唆されたと考え出してみました複雑。

私の場合（私はツリーに組み込まれる約50kのアイテムを持っています）、それは完全に容認できませんでした。

複雑さO（n * log（n））[n回getById、getByIdはO（log（n））を持つ次の解になりました（それぞれの項目に親が1つしかなく、 ））複雑]：

static List<Item> BuildTreeAndReturnRootNodes(List<Item> flatItems) 
{ 
    var byIdLookup = flatItems.ToLookup(i => i.Id); 
    foreach (var item in flatItems) 
    { 
     if (item.ParentId != null) 
     { 
      var parent = byIdLookup[item.ParentId.Value].First(); 
      parent.Children.Add(item); 
     } 
    } 
    return flatItems.Where(i => i.ParentId == null).ToList(); 
} 

完全なコードスニペット：

class Program 
{ 
    static void Main(string[] args) 
    { 
     var flatItems = new List<Item>() 
     { 
      new Item(1), 
      new Item(2), 
      new Item(3, 1), 
      new Item(4, 2), 
      new Item(5, 4), 
      new Item(6, 3), 
      new Item(7, 5), 
      new Item(8, 2), 
      new Item(9, 3), 
      new Item(10, 9), 
     }; 
     var treeNodes = BuildTreeAndReturnRootNodes(flatItems); 
     foreach (var n in treeNodes) 
     { 
      Console.WriteLine(n.Id + " number of children: " + n.Children.Count); 
     } 
    } 
    // Here is the method 
    static List<Item> BuildTreeAndReturnRootNodes(List<Item> flatItems) 
    { 
     var byIdLookup = flatItems.ToLookup(i => i.Id); 
     foreach (var item in flatItems) 
     { 
      if (item.ParentId != null) 
      { 
       var parent = byIdLookup[item.ParentId.Value].First(); 
       parent.Children.Add(item); 
      } 
     } 
     return flatItems.Where(i => i.ParentId == null).ToList(); 
    } 
    class Item 
    { 
     public readonly int Id; 
     public readonly int? ParentId; 

     public Item(int id, int? parent = null) 
     { 
      Id = id; 
      ParentId = parent; 
     } 
     public readonly List<Item> Children = new List<Item>(); 
    } 
}