Rechercher un arbre avec LINQ

Question

J'ai un arbre créé à partir de cette classe.

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

Je veux rechercher dans tous les enfants et tous leurs enfants pour obtenir ceux qui correspondent à une condition:

 node.Key == SomeSpecialKey
 

Comment puis-je le mettre en œuvre?

Answer 1

C'est une idée fausse que cela nécessite de la récursivité. Il faudra une pile ou une file d' attente et le plus simple est de mettre en œuvre à l'aide de la récursivité. Par souci d'exhaustivité, je vais fournir une réponse non récursive.

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

Utilisez cette expression par exemple pour l'utiliser:

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

Answer 2

Rechercher un arbre d'objets avec 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;
        }

    }
}
 

Answer 3

Si vous souhaitez conserver une syntaxe semblable à celle de Linq, vous pouvez utiliser une méthode pour obtenir tous les descendants (enfants + enfants enfants, etc.).

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

Cet énumérable peut ensuite être interrogé comme n'importe quel autre en utilisant où ou en premier ou autre.

Answer 4

Vous pouvez essayer cette méthode d'extension pour énumérer les nœuds d'arborescence:

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

Puis utilisez cela avec une clause Where() :

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

Answer 5

Peut-être vous avez juste besoin

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

Ou, si vous avez besoin de chercher un niveau plus profond,

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

Si vous devez effectuer une recherche à tous les niveaux, procédez comme suit:

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