Buscando un árbol usando LINQ

Tengo un árbol creado a partir de esta clase.

class Node
{
    public string Key { get; }
    public List<Node> Children { get; }
}

Quiero buscar en todos los niños y todos sus niños para obtener los que coinciden con una condición:

node.Key == SomeSpecialKey

¿Cómo puedo implementarlo?

Es un error pensar que esto requiere recursividad. Se va a requerir una pila o una cola y la forma más fácil es para ponerlo en práctica utilizando la recursividad. En aras de la integridad, proporcionaré una respuesta no recursiva.

static IEnumerable<Node> Descendants(this Node root)
{
    var nodes = new Stack<Node>(new[] {root});
    while (nodes.Any())
    {
        Node node = nodes.Pop();
        yield return node;
        foreach (var n in node.Children) nodes.Push(n);
    }
}

Use esta expresión, por ejemplo, para usarla:

root.Descendants().Where(node => node.Key == SomeSpecialKey)

Buscando un árbol de objetos con Linq

public static class TreeToEnumerableEx
{
    public static IEnumerable<T> AsDepthFirstEnumerable<T>(this T head, Func<T, IEnumerable<T>> childrenFunc)
    {
        yield return head;

        foreach (var node in childrenFunc(head))
        {
            foreach (var child in AsDepthFirstEnumerable(node, childrenFunc))
            {
                yield return child;
            }
        }

    }

    public static IEnumerable<T> AsBreadthFirstEnumerable<T>(this T head, Func<T, IEnumerable<T>> childrenFunc)
    {
        yield return head;

        var last = head;
        foreach (var node in AsBreadthFirstEnumerable(head, childrenFunc))
        {
            foreach (var child in childrenFunc(node))
            {
                yield return child;
                last = child;
            }
            if (last.Equals(node)) yield break;
        }

    }
}

Si desea mantener una sintaxis similar a Linq, puede usar un método para obtener todos los descendientes (hijos + hijos de niños, etc.)

static class NodeExtensions
{
    public static IEnumerable<Node> Descendants(this Node node)
    {
        return node.Children.Concat(node.Children.SelectMany(n => n.Descendants()));
    }
}

Este enumerable se puede consultar como cualquier otro utilizando dónde, primero o lo que sea.

Puede probar este método de extensión para enumerar los nodos del árbol:

static IEnumerable<Node> GetTreeNodes(this Node rootNode)
{
    yield return rootNode;
    foreach (var childNode in rootNode.Children)
    {
        foreach (var child in childNode.GetTreeNodes())
            yield return child;
    }
}

Luego usa eso con una Where()cláusula:

var matchingNodes = rootNode.GetTreeNodes().Where(x => x.Key == SomeSpecialKey);

Quizás solo necesites

node.Children.Where(child => child.Key == SomeSpecialKey)

O, si necesita buscar un nivel más profundo,

node.Children.SelectMany(
        child => child.Children.Where(child => child.Key == SomeSpecialKey))

Si necesita buscar en todos los niveles, tome lo siguiente:

IEnumerable<Node> FlattenAndFilter(Node source)
{
    List<Node> l = new List();
    if (source.Key == SomeSpecialKey)
        l.Add(source);
    return
        l.Concat(source.Children.SelectMany(child => FlattenAndFilter(child)));
}

public class Node
    {
        string key;
        List<Node> children;

        public Node(string key)
        {
            this.key = key;
            children = new List<Node>();
        }

        public string Key { get { return key; } }
        public List<Node> Children { get { return children; } }

        public Node Find(Func<Node, bool> myFunc)
        {
            foreach (Node node in Children)
            {
                if (myFunc(node))
                {
                    return node;
                }
                else 
                {
                    Node test = node.Find(myFunc);
                    if (test != null)
                        return test;
                }
            }

            return null;
        }
    }

Y luego puedes buscar como:

    Node root = new Node("root");
    Node child1 = new Node("child1");
    Node child2 = new Node("child2");
    Node child3 = new Node("child3");
    Node child4 = new Node("child4");
    Node child5 = new Node("child5");
    Node child6 = new Node("child6");
    root.Children.Add(child1);
    root.Children.Add(child2);
    child1.Children.Add(child3);
    child2.Children.Add(child4);
    child4.Children.Add(child5);
    child5.Children.Add(child6);

    Node test = root.Find(p => p.Key == "child6");

¿Por qué no utilizar un IEnumerable<T>método de extensión?

public static IEnumerable<TResult> SelectHierarchy<TResult>(this IEnumerable<TResult> source, Func<TResult, IEnumerable<TResult>> collectionSelector, Func<TResult, bool> predicate)
{
    if (source == null)
    {
        yield break;
    }
    foreach (var item in source)
    {
        if (predicate(item))
        {
            yield return item;
        }
        var childResults = SelectHierarchy(collectionSelector(item), collectionSelector, predicate);
        foreach (var childItem in childResults)
        {
            yield return childItem;
        }
    }
}

entonces solo haz esto

var result = nodes.Children.SelectHierarchy(n => n.Children, n => n.Key.IndexOf(searchString) != -1);

Hace un tiempo escribí un artículo de proyecto de código que describe cómo usar Linq para consultar estructuras en forma de árbol:

http://www.codeproject.com/KB/linq/LinqToTree.aspx

Esto proporciona una API de estilo linq-to-XML donde puede buscar descendientes, hijos, antepasados, etc.

Probablemente exagerado para su problema actual, pero podría ser de interés para otros.

Puede utilizar este método de extensión para consultar el árbol.

    public static IEnumerable<Node> InTree(this Node treeNode)
    {
        yield return treeNode;

        foreach (var childNode in treeNode.Children)
            foreach (var flattendChild in InTree(childNode))
                yield return flattendChild;
    }

Tengo un método de extensión genérico que puede aplanar cualquiera IEnumerable<T>y de esa colección aplanada, puede obtener el nodo que desee.

public static IEnumerable<T> FlattenHierarchy<T>(this T node, Func<T, IEnumerable<T>> getChildEnumerator)
{
    yield return node;
    if (getChildEnumerator(node) != null)
    {
        foreach (var child in getChildEnumerator(node))
        {
            foreach (var childOrDescendant in child.FlattenHierarchy(getChildEnumerator))
            {
                yield return childOrDescendant;
            }
        }
    }
}

Usa esto así:

var q = from node in myTree.FlattenHierarchy(x => x.Children)
        where node.Key == "MyKey"
        select node;
var theNode = q.SingleOrDefault();

Utilizo las siguientes implementaciones para enumerar elementos de árbol

    public static IEnumerable<Node> DepthFirstUnfold(this Node root) =>
        ObjectAsEnumerable(root).Concat(root.Children.SelectMany(DepthFirstUnfold));

    public static IEnumerable<Node> BreadthFirstUnfold(this Node root) {
        var queue = new Queue<IEnumerable<Node>>();
        queue.Enqueue(ObjectAsEnumerable(root));

        while (queue.Count != 0)
            foreach (var node in queue.Dequeue()) {
                yield return node;
                queue.Enqueue(node.Children);
            }
    }

    private static IEnumerable<T> ObjectAsEnumerable<T>(T obj) {
        yield return obj;
    }

BreadthFirstUnfold en la implementación anterior usa la cola de secuencias de nodos en lugar de la cola de nodos. Esta no es la forma clásica de algoritmo BFS.

Y solo por diversión (casi una década después) una respuesta que también usa Generics pero con un bucle Stack y While, basada en la respuesta aceptada por @vidstige.

public static class TypeExtentions
{

    public static IEnumerable<T> Descendants<T>(this T root, Func<T, IEnumerable<T>> selector)
    {
        var nodes = new Stack<T>(new[] { root });
        while (nodes.Any())
        {
            T node = nodes.Pop();
            yield return node;
            foreach (var n in selector(node)) nodes.Push(n);
        }
    }

    public static IEnumerable<T> Descendants<T>(this IEnumerable<T> encounter, Func<T, IEnumerable<T>> selector)
    {
        var nodes = new Stack<T>(encounter);
        while (nodes.Any())
        {
            T node = nodes.Pop();
            yield return node;
            if (selector(node) != null)
                foreach (var n in selector(node))
                    nodes.Push(n);
        }
    }
}

Dada una colección, se puede usar así

        var myNode = ListNodes.Descendants(x => x.Children).Where(x => x.Key == SomeKey);

o con un objeto raíz

        var myNode = root.Descendants(x => x.Children).Where(x => x.Key == SomeKey);