Einen Baum (Liste von Listen) mit einer Aussage abflachen?

Question

Dank nHibernate sind einige der Datenstrukturen, mit denen ich arbeite, Listen innerhalb von Listen innerhalb von Listen. So habe ich zum Beispiel ein Datenobjekt namens "category", das eine .Children -Eigenschaft hat, die in eine Liste von Kategorien aufgelöst wird ... von denen jede Kinder haben kann ... und so weiter und so weiter.

Ich muss einen Weg finden, um in einer Top-Level-Kategorie in dieser Struktur zu beginnen und eine Liste oder Array oder etwas Ähnliches von allen Kindern in der gesamten Struktur zu bekommen - also alle Kinder aller Kinder usw. etc, abgeflacht in eine einzige Liste.

Ich bin mir sicher, dass es mit Rekursion getan werden kann, aber ich finde rekursive Code einen Schmerz zu arbeiten, und ich bin davon überzeugt, es muss einen einfacheren Weg in .Net 4 mit Linq oder Somesuch - irgendwelche Vorschläge?

Answer 1

Ihre Kategorie Klasse sieht aus wie etwas Angenommen:

public class Category 
{ 
    public string Name { get; set; } 
    public List<Category> Children { get; set; } 
} 

Ich glaube nicht, dass es eine „easy“ nicht-rekursive Art und Weise, es zu tun ist; Wenn Sie nur nach einem einzelnen Methodenaufruf suchen, um damit umzugehen, besteht der "einfache" Weg darin, die rekursive Version in einen einzigen Methodenaufruf zu schreiben. Es gibt wahrscheinlich einen iterativen Weg, um das zu tun, aber ich schätze, es ist eigentlich ziemlich kompliziert. Es ist so, als würde man nach dem "einfachen" Weg fragen, um eine Tangente an eine Kurve zu finden, ohne Kalkül zu verwenden.

Wie dem auch sei, würde dies wahrscheinlich tun es:

public static List<Category> Flatten(Category root) { 

    var flattened = new List<Category> {root}; 

    var children = root.Children; 

    if(children != null) 
    { 
     foreach (var child in children) 
     { 
      flattened.AddRange(Flatten(child)); 
     } 
    } 

    return flattened; 
} 

Answer 2

Hier ist eine Erweiterung Methode, die die Arbeit erledigt:

// Depth-first traversal, recursive 
public static IEnumerable<T> Flatten<T>(
     this IEnumerable<T> source, 
     Func<T, IEnumerable<T>> childrenSelector) 
{ 
    foreach (var item in source) 
    { 
     yield return item; 
     foreach (var child in childrenSelector(item).Flatten(childrenSelector)) 
     { 
      yield return child; 
     } 
    } 
} 

Sie können es wie folgt verwenden:

foreach(var category in categories.Flatten(c => c.Children)) 
{ 
    ... 
} 

Die Lösung oben tut eine Tiefe-zuerst-Traversal, wenn Sie eine Breite-zuerst-Traversal können Sie etwas wie th tun ist:

// Breadth-first traversal, non-recursive 
public static IEnumerable<T> Flatten2<T>(
     this IEnumerable<T> source, 
     Func<T, IEnumerable<T>> childrenSelector) 
{ 
    var queue = new Queue<T>(source); 
    while (queue.Count > 0) 
    { 
     var item = queue.Dequeue(); 
     yield return item; 
     foreach (var child in childrenSelector(item)) 
     { 
      queue.Enqueue(child); 
     } 
    } 
} 

Es hat auch den Vorteil, dass nicht-rekursive ...

---

UPDATE: Eigentlich dachte ich nur eine Möglichkeit, die depth-first Traversal nicht-rekursive zu machen. hier .. es ist:

// Depth-first traversal, non-recursive 
public static IEnumerable<T> Flatten3<T>(
     this IEnumerable<T> source, 
     Func<T, IEnumerable<T>> childrenSelector) 
{ 
    LinkedList<T> list = new LinkedList<T>(source); 
    while (list.Count > 0) 
    { 
     var item = list.First.Value; 
     yield return item; 
     list.RemoveFirst(); 
     var node = list.First; 
     foreach (var child in childrenSelector(item)) 
     { 
      if (node != null) 
       list.AddBefore(node, child); 
      else 
       list.AddLast(child); 
     } 
    } 
} 

ich bin ein mit LinkedList<T> weil Einfügungen O (1) Operationen sind, während Einfügungen in einem List<T> O sind (n).

Answer 3

Wenn Breath-First-Traversal OK ist und Sie nur einen kurzen nicht-rekursiven Inline-Code (eigentlich 3 Zeilen) verwenden möchten, erstellen Sie eine mit Ihrem Root-Element initialisierte Liste und erweitern Sie sie dann um ein einfaches for -loop:

// your data object class looks like: 
public class DataObject 
{ 
    public List<DataObject> Children { get; set; } 
    ... 
} 

... 

// given are some root elements 
IEnumerable<DataObject> rootElements = ... 

// initialize the flattened list with the root elements 
var result = new List<DataObject>(rootElements); 
// extend the flattened list by one simple for-loop, 
// please note that result.Count may increase after every iteration! 
for (int index = 0; index < result.Count; index++) 
    result.AddRange(result[index].Children); 

Answer 4

die Klasse gegeben @EZHart erwähnt, könnten Sie erweitern es auch mit einem Helfer-Methode für das was ich denke, ist in diesem Fall einfacher.

public class Category 
{ 
    public string Name { get; set; } 

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

    public IEnumerable<Category> AllChildren() 
    { 
     yield return this; 
     foreach (var child in Children) 
     foreach (var granChild in child.AllChildren()) 
     { 
      yield return granChild; 
     } 
    } 
}