Cómo aplanar el árbol a través de LINQ?

Así que tengo un árbol simple:

class MyNode { public MyNode Parent; public IEnumerable Elements; int group = 1; } 

Tengo un IEnumerable . Quiero obtener una lista de todos los MyNode (incluidos los objetos del nodo interno ( Elements )) como una lista plana Where group == 1 . ¿Cómo hacer tal cosa a través de LINQ?

Puedes aplanar un árbol como este:

 IEnumerable Flatten(IEnumerable e) { return e.SelectMany(c => Flatten(c.Elements)).Concat(new[] {e}); } 

Luego puede filtrar por group usando Where(...) .

Para ganar algunos “puntos por estilo”, convierta Flatten a una función de extensión en una clase estática.

 public static IEnumerable Flatten(this IEnumerable e) { return e.SelectMany(c => c.Elements.Flatten()).Concat(e); } 

Para ganar algunos puntos por “aún mejor estilo”, convierta Flatten a un método de extensión genérico que toma un árbol y una función que produce descendientes:

 public static IEnumerable Flatten( this IEnumerable e, Func> f) { return e.SelectMany(c => f(c).Flatten(f)).Concat(e); } 

Llame a esta función de esta manera:

 IEnumerable tree = .... var res = tree.Flatten(node => node.Elements); 

Si prefiere aplanar en prepedido en lugar de hacerlo después, cambie los lados del Concat(...) .

El problema con la respuesta aceptada es que es ineficiente si el árbol es profundo. Si el árbol es muy profundo, sopla la stack. Puede resolver el problema utilizando una stack explícita:

 public static IEnumerable Traverse(this MyNode root) { var stack = new Stack(); stack.Push(root); while(stack.Count > 0) { var current = stack.Pop(); yield return current; foreach(var child in current.Elements) stack.Push(child); } } 

Asumiendo n nodos en un árbol de altura h y un factor de ramificación considerablemente menor que n, este método es O (1) en el espacio de stack, O (h) en el espacio de stack y O (n) en el tiempo. El otro algoritmo dado es O (h) en la stack, O (1) en el montón y O (nh) en el tiempo. Si el factor de ramificación es pequeño en comparación con n, h está entre O (lg n) y O (n), lo que ilustra que el algoritmo ingenuo puede usar una cantidad peligrosa de astackmiento y una gran cantidad de tiempo si h está cerca de n.

Ahora que tenemos un recorrido, su consulta es sencilla:

 root.Traverse().Where(item=>item.group == 1); 

Para completar, aquí está la combinación de las respuestas de dasblinkenlight y Eric Lippert. Unidad probada y todo. 🙂

  public static IEnumerable Flatten( this IEnumerable items, Func> getChildren) { var stack = new Stack(); foreach(var item in items) stack.Push(item); while(stack.Count > 0) { var current = stack.Pop(); yield return current; var children = getChildren(current); if (children == null) continue; foreach (var child in children) stack.Push(child); } } 

Actualizar:

Para personas interesadas en el nivel de anidación (profundidad). Una de las cosas buenas acerca de la implementación explícita de la stack de enumeradores es que en cualquier momento (y en particular cuando cede el elemento) stack.Count representa la profundidad de procesamiento actual. Por lo tanto, teniendo esto en cuenta y utilizando las tuplas de valores de C # 7.0, simplemente podemos cambiar la statement del método de la siguiente manera:

 public static IEnumerable<(T Item, int Level)> ExpandWithLevel( this IEnumerable source, Func> elementSelector) 

y statement de yield :

 yield return (item, stack.Count); 

Luego podemos implementar el método original aplicando Select simple en el cuadro anterior:

 public static IEnumerable Expand( this IEnumerable source, Func> elementSelector) => source.ExpandWithLevel(elementSelector).Select(e => e.Item); 

Original:

Sorprendentemente, nadie (ni siquiera Eric) mostró el puerto iterativo “natural” de un DFT preordenador recursivo, así que aquí está:

  public static IEnumerable Expand( this IEnumerable source, Func> elementSelector) { var stack = new Stack>(); var e = source.GetEnumerator(); try { while (true) { while (e.MoveNext()) { var item = e.Current; yield return item; var elements = elementSelector(item); if (elements == null) continue; stack.Push(e); e = elements.GetEnumerator(); } if (stack.Count == 0) break; e.Dispose(); e = stack.Pop(); } } finally { e.Dispose(); while (stack.Count != 0) stack.Pop().Dispose(); } } 

En caso de que alguien más encuentre esto, pero también necesita saber el nivel después de haber aplanado el árbol, esto se amplía con la combinación de dasblinkenlight y las soluciones de Eric Lippert de Konamiman:

  public static IEnumerable> FlattenWithLevel( this IEnumerable items, Func> getChilds) { var stack = new Stack>(); foreach (var item in items) stack.Push(new Tuple(item, 1)); while (stack.Count > 0) { var current = stack.Pop(); yield return current; foreach (var child in getChilds(current.Item1)) stack.Push(new Tuple(child, current.Item2 + 1)); } } 

Encontré algunos pequeños problemas con las respuestas dadas aquí:

  • ¿Qué pasa si la lista inicial de artículos es nula?
  • ¿Qué sucede si hay un valor nulo en la lista de hijos?

Construido sobre las respuestas anteriores y se produjo lo siguiente:

 public static class IEnumerableExtensions { public static IEnumerable Flatten( this IEnumerable items, Func> getChildren) { if (items == null) yield break; var stack = new Stack(items); while (stack.Count > 0) { var current = stack.Pop(); yield return current; if (current == null) continue; var children = getChildren(current); if (children == null) continue; foreach (var child in children) stack.Push(child); } } } 

Y la unidad prueba:

 [TestClass] public class IEnumerableExtensionsTests { [TestMethod] public void NullList() { IEnumerable items = null; var flattened = items.Flatten(i => i.Children); Assert.AreEqual(0, flattened.Count()); } [TestMethod] public void EmptyList() { var items = new Test[0]; var flattened = items.Flatten(i => i.Children); Assert.AreEqual(0, flattened.Count()); } [TestMethod] public void OneItem() { var items = new[] { new Test() }; var flattened = items.Flatten(i => i.Children); Assert.AreEqual(1, flattened.Count()); } [TestMethod] public void OneItemWithChild() { var items = new[] { new Test { Id = 1, Children = new[] { new Test { Id = 2 } } } }; var flattened = items.Flatten(i => i.Children); Assert.AreEqual(2, flattened.Count()); Assert.IsTrue(flattened.Any(i => i.Id == 1)); Assert.IsTrue(flattened.Any(i => i.Id == 2)); } [TestMethod] public void OneItemWithNullChild() { var items = new[] { new Test { Id = 1, Children = new Test[] { null } } }; var flattened = items.Flatten(i => i.Children); Assert.AreEqual(2, flattened.Count()); Assert.IsTrue(flattened.Any(i => i.Id == 1)); Assert.IsTrue(flattened.Any(i => i == null)); } class Test { public int Id { get; set; } public IEnumerable Children { get; set; } } } 

La forma más fácil / más clara de abordar esto es usar una consulta LINQ recursiva. Esta pregunta: Expresar la recursividad en LINQ tiene mucha discusión sobre esto, y esta respuesta en particular https://stackoverflow.com/a/793531/1550 explica en detalle cómo implementarla.

 void Main() { var allNodes = GetTreeNodes().Flatten(x => x.Elements); allNodes.Dump(); } public static class ExtensionMethods { public static IEnumerable Flatten(this IEnumerable source, Func> childrenSelector = null) { if (source == null) { return new List(); } var list = source; if (childrenSelector != null) { foreach (var item in source) { list = list.Concat(childrenSelector(item).Flatten(childrenSelector)); } } return list; } } IEnumerable GetTreeNodes() { return new[] { new MyNode { Elements = new[] { new MyNode() }}, new MyNode { Elements = new[] { new MyNode(), new MyNode(), new MyNode() }} }; } class MyNode { public MyNode Parent; public IEnumerable Elements; int group = 1; } 

Combinando la respuesta de Dave e Ivan Stoev en caso de que necesite el nivel de anidación y la lista aplanada “en orden” y no invertida como en la respuesta dada por Konamiman.

  public static class HierarchicalEnumerableUtils { private static IEnumerable> ToLeveled(this IEnumerable source, int level) { if (source == null) { return null; } else { return source.Select(item => new Tuple(item, level)); } } public static IEnumerable> FlattenWithLevel(this IEnumerable source, Func> elementSelector) { var stack = new Stack>>(); var leveledSource = source.ToLeveled(0); var e = leveledSource.GetEnumerator(); try { while (true) { while (e.MoveNext()) { var item = e.Current; yield return item; var elements = elementSelector(item.Item1).ToLeveled(item.Item2 + 1); if (elements == null) continue; stack.Push(e); e = elements.GetEnumerator(); } if (stack.Count == 0) break; e.Dispose(); e = stack.Pop(); } } finally { e.Dispose(); while (stack.Count != 0) stack.Pop().Dispose(); } } } 

Sobre la base de la respuesta de Konamiman, y el comentario de que el orden es inesperado, aquí hay una versión con un param tipo explícito:

 public static IEnumerable TraverseAndFlatten(this IEnumerable items, Func> nested, Func orderBy) { var stack = new Stack(); foreach (var item in items.OrderBy(orderBy)) stack.Push(item); while (stack.Count > 0) { var current = stack.Pop(); yield return current; var children = nested(current).OrderBy(orderBy); if (children == null) continue; foreach (var child in children) stack.Push(child); } } 

Y un uso de muestra:

 var flattened = doc.TraverseAndFlatten(x => x.DependentDocuments, y => y.Document.DocDated).ToList(); 

A continuación se muestra el código de Ivan Stoev con la característica adicional de indicar el índice de cada objeto en la ruta. Por ejemplo, busque “Item_120”:

 Item_0--Item_00 Item_01 Item_1--Item_10 Item_11 Item_12--Item_120 

devolvería el artículo y una matriz int [1,2,0]. Obviamente, el nivel de anidación también está disponible, como la longitud de la matriz.

 public static IEnumerable<(T, int[])> Expand(this IEnumerable source, Func> getChildren) { var stack = new Stack>(); var e = source.GetEnumerator(); List indexes = new List() { -1 }; try { while (true) { while (e.MoveNext()) { var item = e.Current; indexes[stack.Count]++; yield return (item, indexes.Take(stack.Count + 1).ToArray()); var elements = getChildren(item); if (elements == null) continue; stack.Push(e); e = elements.GetEnumerator(); if (indexes.Count == stack.Count) indexes.Add(-1); } if (stack.Count == 0) break; e.Dispose(); indexes[stack.Count] = -1; e = stack.Pop(); } } finally { e.Dispose(); while (stack.Count != 0) stack.Pop().Dispose(); } }