¿Cómo aplanar el árbol a través de LINQ?
Entonces tengo un árbol simple:
class MyNode
{
public MyNode Parent;
public IEnumerable<MyNode> Elements;
int group = 1;
}
Tengo un IEnumerable<MyNode>. Quiero obtener una lista de todos 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<MyNode> Flatten(IEnumerable<MyNode> e) =>
e.SelectMany(c => Flatten(c.Elements)).Concat(new[] { e });
Luego puedes filtrar groupusando Where(...).
Para ganar algunos "puntos por estilo", conviértalo Flattena una función de extensión en una clase estática.
public static IEnumerable<MyNode> Flatten(this IEnumerable<MyNode> e) =>
e.SelectMany(c => c.Elements.Flatten()).Concat(e);
Para ganar más puntos por un "estilo aún mejor", convierta Flattena un método de extensión genérico que toma un árbol y una función que produce descendientes de un nodo:
public static IEnumerable<T> Flatten<T>(
this IEnumerable<T> e
, Func<T,IEnumerable<T>> f
) => e.SelectMany(c => f(c).Flatten(f)).Concat(e);
Llame a esta función así:
IEnumerable<MyNode> tree = ....
var res = tree.Flatten(node => node.Elements);
Si prefiere aplanar en el pedido anticipado en lugar de en el pedido posterior, cambie los lados del archivo Concat(...).
El problema con la respuesta aceptada es que es ineficiente si el árbol es profundo. Si el árbol es muy profundo entonces vuela la pila. Puedes resolver el problema usando una pila explícita:
public static IEnumerable<MyNode> Traverse(this MyNode root)
{
var stack = new Stack<MyNode>();
stack.Push(root);
while(stack.Count > 0)
{
var current = stack.Pop();
yield return current;
foreach(var child in current.Elements)
stack.Push(child);
}
}
Suponiendo 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 la pila, O(h) en el espacio del montón y O(n) en el tiempo. El otro algoritmo proporcionado es O(h) en pila, O(1) en montón y O(nh) en tiempo. Si el factor de ramificación es pequeño en comparación con n, entonces h está entre O(lg n) y O(n), lo que ilustra que el algoritmo ingenuo puede utilizar una cantidad peligrosa de pila 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<T> Flatten<T>(
this IEnumerable<T> items,
Func<T, IEnumerable<T>> getChildren)
{
var stack = new Stack<T>();
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 anidamiento (profundidad). Una de las cosas buenas de la implementación explícita de la pila de enumerador es que en cualquier momento (y en particular cuando se genera el elemento) stack.Countrepresenta la profundidad de procesamiento actual. Entonces, teniendo esto en cuenta y utilizando las tuplas de valores de C#7.0, simplemente podemos cambiar la declaración del método de la siguiente manera:
public static IEnumerable<(T Item, int Level)> ExpandWithLevel<T>(
this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector)
y yielddeclaración:
yield return (item, stack.Count);
Luego podemos implementar el método original aplicando Selectlo anterior:
public static IEnumerable<T> Expand<T>(
this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector) =>
source.ExpandWithLevel(elementSelector).Select(e => e.Item);
Original:
Sorprendentemente, nadie (ni siquiera Eric) mostró el puerto iterativo "natural" de un DFT de pedido anticipado recursivo, así que aquí está:
public static IEnumerable<T> Expand<T>(
this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector)
{
var stack = new Stack<IEnumerator<T>>();
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();
}
}
