Durchsuchen eines Baums mit LINQ

87

Ich habe einen Baum aus dieser Klasse erstellt.

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

Ich möchte alle Kinder und alle ihre Kinder durchsuchen, um diejenigen zu finden, die einer Bedingung entsprechen:

node.Key == SomeSpecialKey

Wie kann ich es implementieren?

Ufuk Hacıoğulları
quelle
Interessant, ich denke, Sie können dies mit der SelectMany-Funktion erreichen. Denken Sie daran, dass Sie vor einiger Zeit etwas Ähnliches tun müssen.
Jethro

Antworten:

175

Es ist ein Missverständnis, dass dies eine Rekursion erfordert. Es wird einen Stapel oder eine Warteschlange erfordern, und der einfachste Weg besteht darin, ihn mithilfe der Rekursion zu implementieren. Der Vollständigkeit halber werde ich eine nicht rekursive Antwort geben.

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

Verwenden Sie diesen Ausdruck zum Beispiel, um ihn zu verwenden:

root.Descendants().Where(node => node.Key == SomeSpecialKey)
vidstige
quelle
31
+1. Und diese Methode funktioniert weiterhin, wenn der Baum so tief ist, dass eine rekursive Durchquerung den Aufrufstapel sprengt und a verursacht StackOverflowException.
LukeH
3
@LukeH Obwohl es für solche Situationen nützlich ist, solche Alternativen zu haben, würde dies einen sehr großen Baum bedeuten. Sofern Ihr Baum nicht sehr tief ist, sind die rekursiven Methoden normalerweise einfacher / besser lesbar.
ForbesLindesay
3
@Tuskan: Die Verwendung rekursiver Iteratoren hat auch Auswirkungen auf die Leistung, siehe Abschnitt "Die Kosten von Iteratoren" auf blogs.msdn.com/b/wesdyer/archive/2007/03/23/… (zugegebenermaßen müssen die Bäume noch ziemlich tief sein dies fällt auf). Und fwiw, ich finde die Antwort von vidstige genauso lesbar wie die rekursiven Antworten hier.
LukeH
3
Ja, wählen Sie meine Lösung nicht wegen der Leistung. Die Lesbarkeit steht immer an erster Stelle, es sei denn, es liegt ein Engpass vor. Obwohl meine Lösung ziemlich einfach ist, denke ich, ist es Geschmackssache ... Ich habe meine Antwort tatsächlich nur als Ergänzung zu den rekursiven Antworten gepostet, aber ich bin froh, dass es den Leuten gefallen hat.
Vidstige
11
Ich denke, es ist erwähnenswert, dass die oben vorgestellte Lösung eine Tiefensuche (letztes Kind zuerst) durchführt. Wenn Sie eine (First-Child-First) Breitensuche wünschen, können Sie den Typ der Knotensammlung in Queue<Node>(mit den entsprechenden Änderungen an Enqueue/ Dequeuevon Push/ Pop) ändern .
Andrew Coonce
16

Durchsuchen eines Objektbaums mit 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;
        }

    }
}
CD..
quelle
1
+1 Löst das Problem im Allgemeinen. Der verlinkte Artikel lieferte eine gute Erklärung.
John Jesus
Um vollständig zu sein, müssen Sie die Parameter auf Null prüfen headund childrenFuncdie Methoden in zwei Teile aufteilen, damit die Parameterprüfung nicht auf die Durchlaufzeit verschoben wird.
ErikE
15

Wenn Sie die Linq-ähnliche Syntax beibehalten möchten, können Sie eine Methode verwenden, um alle Nachkommen (Kinder + Kinder Kinder usw.) zu erhalten.

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

Diese Aufzählung kann dann wie jede andere mit where oder first oder was auch immer abgefragt werden.

ForbesLindesay
quelle
Ich mag das, sauber! :)
vidstige
3

Sie können diese Erweiterungsmethode ausprobieren, um die Baumknoten aufzulisten:

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

Verwenden Sie das dann mit einer Where()Klausel:

var matchingNodes = rootNode.GetTreeNodes().Where(x => x.Key == SomeSpecialKey);
dlev
quelle
2
Beachten Sie, dass diese Technik ineffizient ist, wenn der Baum tief ist, und eine Ausnahme auslösen kann, wenn der Baum sehr tief ist.
Eric Lippert
1
@ Eric Guter Punkt. Und willkommen zurück aus dem Urlaub? (Es ist schwer zu sagen, was mit diesem Internet-Ding auf der ganzen Welt.)
dlev
2

Vielleicht brauchst du nur

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

Oder, wenn Sie eine Ebene tiefer suchen müssen,

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

Wenn Sie auf allen Ebenen suchen müssen, gehen Sie wie folgt vor:

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)));
}
Vlad
quelle
Wird das die Kinder der Kinder durchsuchen?
Jethro
Ich denke, das wird nicht funktionieren, da dies nur auf einer Ebene im Baum sucht und keine vollständige Baumdurchquerung durchführt
lunactic
@Ufuk: Die 1. Zeile arbeitet nur 1 Ebene tief, die zweite nur 2 Ebenen tief. Wenn Sie auf allen Ebenen suchen müssen , benötigen Sie eine rekursive Funktion.
Vlad
2
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;
        }
    }

Und dann können Sie suchen wie:

    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");
Varun Chatterji
quelle
Da die Eingabe von Find Func <Node, bool> myFunc ist, können Sie diese Methode verwenden, um nach jeder anderen Eigenschaft zu filtern, die Sie möglicherweise auch in Node definieren. Zum Beispiel in Node hatte eine Name-Eigenschaft und Sie wollten einen Node by Name finden, Sie könnten einfach p => p.Name == "Something"
Varun Chatterji
2

Warum nicht eine IEnumerable<T>Erweiterungsmethode verwenden?

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

dann mach das einfach

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

Vor einiger Zeit schrieb ich einen Artikel über ein Codeprojekt, in dem beschrieben wird, wie mit Linq baumartige Strukturen abgefragt werden:

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

Dies bietet eine Linq-to-XML-API, mit der Sie Nachkommen, Kinder, Vorfahren usw. suchen können.

Wahrscheinlich übertrieben für Ihr aktuelles Problem, könnte aber für andere von Interesse sein.

ColinE
quelle
0

Mit dieser Erweiterungsmethode können Sie den Baum abfragen.

    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;
    }
BitKFu
quelle
0

Ich habe eine generische Erweiterungsmethode, die jede reduzieren kann, IEnumerable<T>und aus dieser reduzierten Sammlung können Sie den gewünschten Knoten erhalten.

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

Verwenden Sie dies wie folgt:

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

Ich verwende die folgenden Implementierungen zum Auflisten von Tree-Elementen

    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 verwendet in der obigen Implementierung die Warteschlange der Knotensequenzen anstelle der Knotenwarteschlange. Dies ist kein klassischer BFS-Algorithmus.

Valentine Zakharenko
quelle
0

Und nur zum Spaß (fast ein Jahrzehnt später) eine Antwort, die ebenfalls Generics verwendet, jedoch eine Stack- und While-Schleife enthält, basierend auf der akzeptierten Antwort von @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);
        }
    }
}

Bei einer Sammlung kann man diese verwenden

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

oder mit einem Stammobjekt

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