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?
Antworten:
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.
Verwenden Sie diesen Ausdruck zum Beispiel, um ihn zu verwenden:
quelle
StackOverflowException
.Queue<Node>
(mit den entsprechenden Änderungen anEnqueue
/Dequeue
vonPush
/Pop
) ändern .Durchsuchen eines Objektbaums mit Linq
quelle
head
undchildrenFunc
die Methoden in zwei Teile aufteilen, damit die Parameterprüfung nicht auf die Durchlaufzeit verschoben wird.Wenn Sie die Linq-ähnliche Syntax beibehalten möchten, können Sie eine Methode verwenden, um alle Nachkommen (Kinder + Kinder Kinder usw.) zu erhalten.
Diese Aufzählung kann dann wie jede andere mit where oder first oder was auch immer abgefragt werden.
quelle
Sie können diese Erweiterungsmethode ausprobieren, um die Baumknoten aufzulisten:
Verwenden Sie das dann mit einer
Where()
Klausel:quelle
Vielleicht brauchst du nur
Oder, wenn Sie eine Ebene tiefer suchen müssen,
Wenn Sie auf allen Ebenen suchen müssen, gehen Sie wie folgt vor:
quelle
Und dann können Sie suchen wie:
quelle
Warum nicht eine
IEnumerable<T>
Erweiterungsmethode verwenden?dann mach das einfach
quelle
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.
quelle
Mit dieser Erweiterungsmethode können Sie den Baum abfragen.
quelle
Ich habe eine generische Erweiterungsmethode, die jede reduzieren kann,
IEnumerable<T>
und aus dieser reduzierten Sammlung können Sie den gewünschten Knoten erhalten.Verwenden Sie dies wie folgt:
quelle
Ich verwende die folgenden Implementierungen zum Auflisten von Tree-Elementen
BreadthFirstUnfold verwendet in der obigen Implementierung die Warteschlange der Knotensequenzen anstelle der Knotenwarteschlange. Dies ist kein klassischer BFS-Algorithmus.
quelle
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.
Bei einer Sammlung kann man diese verwenden
oder mit einem Stammobjekt
quelle