¿Acoplar un árbol (lista de listas) con una sola declaración?

Question

Gracias a nHibernate, algunas de las estructuras de datos con las que trabajo son listas dentro de listas dentro de listas. Entonces, por ejemplo, tengo un objeto de datos llamado "categoría" que tiene una propiedad .Children que se resuelve en una lista de categorías ... cada una de las cuales puede tener hijos ... y así sucesivamente.

Necesito encontrar una manera de comenzar en una categoría de nivel superior en esta estructura y obtener una lista o matriz o algo similar de todos los niños en toda la estructura, así que todos los hijos de todos los niños, etc. aplanado en una sola lista.

Estoy seguro de que se puede hacer con recursividad, pero me resulta difícil trabajar con el código recursivo, y estoy convencido de que debe ser una forma más directa en .Net 4 utilizando Linq o somesuch, ¿alguna sugerencia?

Answer 1

Asumiendo que su clase Categoría ve algo como:

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

No creo que hay una manera "fácil" no recursivo para hacerlo; si simplemente está buscando una llamada de método único para manejarlo, la forma "fácil" es escribir la versión recursiva en una sola llamada a método. Probablemente haya una manera iterativa de hacer esto, pero supongo que en realidad es bastante complicado. Es como preguntar la forma "fácil" de encontrar una tangente a una curva sin usar cálculo.

De todos modos, esto probablemente hacerlo:

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

Aquí es un método de extensión que hace el trabajo:

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

Usted puede utilizar de esta manera:

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

El La solución anterior realiza un recorrido en profundidad, si desea un recorrido transversal en amplitud puede hacer algo como es:

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

También tiene la ventaja de ser no recursivo ...

---

ACTUALIZACIÓN: En realidad, me acaba de ocurrir una manera de hacer el recorrido en profundidad no recursivo. .. aquí está:

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

estoy usando un LinkedList<T> porque inserciones son O (1) operaciones, mientras que las inserciones a un List<T> son O (n).

Answer 3

Si la transición de ancho es correcta y solo desea utilizar un código en línea corto no recursivo (3 líneas en realidad), cree una lista inicializada con su (s) elemento (s) raíz y luego amplíela con solo un simple -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

Dada la clase @EZHart menciona, también se puede extender con un método de ayuda para este que creo que es más simple en este caso.

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