Build Baum Typ Liste durch rekursive Prüfung Eltern-Kind-Beziehung C#

Question

Ich habe eine Klasse, die eine Liste von sich selbst, so dass es in einer Baumstruktur dargestellt werden kann.

Ich ziehe eine flache Liste dieser Klassen und möchte sie aufklappen.

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

    public int? ParentID {get;set;} 

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

} 

Ich mag folgende

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

Die ParentID Lage sein, die ID-Eigenschaft auf seiner Stammgruppe offensichtlich, wenn das ist nicht im Zusammenhang zu tun.

EDIT

Es gibt einige Verwirrung darüber, warum ich eine Liste und nicht ein einzelnes Objekt zurückkehre.

Ich baue ein UI-Element, das eine Liste von Elementen hat, von denen jedes ein Kind hat. Die erste Liste hat also keinen Wurzelknoten. Es scheint, dass alle Lösungen bisher nicht funktionieren.

Was das bedeutet ist, ich brauche im Wesentlichen eine Liste von Baumtyp Strukturen mit Group-Klasse.

Answer 1

Ich habe keine Ahnung, warum Sie Ihre BuildTree Methode Rückkehr List<Group> wollen - Baum-Stammknoten haben muss, Sie sollten also erwarten, dass das Element Group Element zurückgegeben wird, keine Liste.

würde ich eine Erweiterungsmethode auf IEnumerable<Group> erstellen:

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

Nutzungs

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

Hier ist, wie Sie dies in einer Zeile tun:

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

Sie können es einfach so nennen:

BuildTree(flatList); 

Wenn am Ende Sie die Knoten, deren Eltern bekommen wollen, ist null (dh die Knoten der obersten Ebene), können Sie einfach tun:

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

Und wenn Sie es eine Erweiterungsmethode machen möchten, können Sie fügen Sie einfach this in der Methodensignatur:

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

Dann sind Sie es so nennen kann:

var roots = flatList.BuildTree(); 

Answer 3

Ich habe versucht, Lösungen vorgeschlagen und herausgefunden, dass sie uns über O (n^2) Komplexität.

In meinem Fall (ich habe etwa 50k Elemente in den Baum gebaut werden) war es völlig inakzeptabel.

Ich kam zu der folgenden Lösung (angenommen, dass jedes Element nur ein Elternteil hat und alle Eltern in der Liste vorhanden sind) mit Komplexität O (n * log (n)) [n mal getById, getById hat O (log (n)) Komplexität]:

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

Voll Code-Schnipsel:

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