Wyszukiwanie drzewa za pomocą LINQ
Mam drzewo stworzone z tej klasy.
class Node
{
public string Key { get; }
public List<Node> Children { get; }
}
Chcę przeszukać wszystkie dzieci i wszystkie ich dzieci, aby uzyskać te pasujące do warunku:
node.Key == SomeSpecialKey
Jak mogę to zaimplementować?
12 answers
Jest błędne przekonanie, że wymaga to rekurencji. To będzie wymagało stosu lub kolejki i najprostszym sposobem jest zaimplementowanie go za pomocą rekurencji. Dla kompletności podam odpowiedź Nie rekurencyjną.
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);
}
}
Użyj tego wyrażenia na przykład, aby go użyć:
root.Descendants().Where(node => node.Key == SomeSpecialKey)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-11-05 20:10:18
Wyszukiwanie drzewa obiektów za pomocą 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;
}
}
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-08-20 23:02:38
Jeśli chcesz zachować składnię podobną do Linq, możesz użyć metody do uzyskania wszystkich potomków (children + children ' s children itp.)
static class NodeExtensions
{
public static IEnumerable<Node> Descendants(this Node node)
{
return node.Children.Concat(node.Children.SelectMany(n => n.Descendants()));
}
}
To wyliczenie może być następnie zapytane jak każde inne użycie where, first lub whatever.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-08-15 08:35:26
Możesz wypróbować tę metodę rozszerzenia, aby wyliczyć węzły drzewa:
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;
}
}
Następnie użyj tego z Where()
klauzuli:
var matchingNodes = rootNode.GetTreeNodes().Where(x => x.Key == SomeSpecialKey);
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-08-15 08:38:21
Być może potrzebujesz tylko
node.Children.Where(child => child.Key == SomeSpecialKey)
Lub, jeśli potrzebujesz przeszukać jeden poziom głębiej,
node.Children.SelectMany(
child => child.Children.Where(child => child.Key == SomeSpecialKey))
Jeśli potrzebujesz szukać na wszystkich poziomach, wykonaj następujące czynności:
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)));
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-08-15 08:41:31
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;
}
}
A następnie możesz wyszukać w stylu:
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");
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-08-15 08:47:28
Dlaczego nie użyć metody rozszerzeniaIEnumerable<T>
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;
}
}
}
Więc zrób to
var result = nodes.Children.SelectHierarchy(n => n.Children, n => n.Key.IndexOf(searchString) != -1);
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-08-15 09:08:19
Jakiś czas temu napisałem artykuł codeproject, który opisuje jak używać Linq do zapytań o struktury podobne do drzewa:
Http://www.codeproject.com/KB/linq/LinqToTree.aspx
Zapewnia to API w stylu linq-to-XML, w którym można wyszukiwać Potomków, dzieci, przodków itp...
Prawdopodobnie przesada z Twoim obecnym problemem, ale może zainteresować innych.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-08-15 08:30:43
Możesz użyć tej metody rozszerzenia do zapytania drzewa.
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;
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-08-15 08:40:01
Mam generyczną metodę rozszerzenia, która może spłaszczyć dowolny IEnumerable<T>
i z tej spłaszczonej kolekcji możesz uzyskać węzeł, który chcesz.
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;
}
}
}
}
Użyj tego tak:
var q = from node in myTree.FlattenHierarchy(x => x.Children)
where node.Key == "MyKey"
select node;
var theNode = q.SingleOrDefault();
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-08-15 08:46:22
Używam następujących implementacji do wyliczania elementów drzewa
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;
}
Widthfirstunfold w implementacji powyżej używa kolejki sekwencji węzłów zamiast kolejki węzłów. Nie jest to klasyczny sposób algorytmu BFS.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-04-05 10:30:34
I dla Zabawy (prawie dekadę później) odpowiedź również za pomocą generyków, ale ze stosem i pętlą While, na podstawie zaakceptowanej odpowiedzi przez @ 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);
}
}
}
Biorąc pod uwagę zbiór można użyć w ten sposób
var myNode = ListNodes.Descendants(x => x.Children).Where(x => x.Key == SomeKey);
Lub z obiektem root
var myNode = root.Descendants(x => x.Children).Where(x => x.Key == SomeKey);
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2019-11-06 15:07:17