使用LINQ搜索树

Question

我有一个从该类创建的树。

class Node

{

    public string Key { get; }

    public List<Node> Children { get; }

}

我想搜索所有孩子及其所有孩子，以找到符合条件的孩子：

node.Key == SomeSpecialKey

我该如何实施？

Answer 1

这需要递归是一个误解。这将需要一个堆栈或队列和最简单的方法是使用递归来实现它。为了完整起见，我将提供一个非递归答案。static IEnumerable<Node> Descendants(this Node root){&nbsp; &nbsp; var nodes = new Stack<Node>(new[] {root});&nbsp; &nbsp; while (nodes.Any())&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; Node node = nodes.Pop();&nbsp; &nbsp; &nbsp; &nbsp; yield return node;&nbsp; &nbsp; &nbsp; &nbsp; foreach (var n in node.Children) nodes.Push(n);&nbsp; &nbsp; }}例如，使用以下表达式来使用它：root.Descendants().Where(node => node.Key == SomeSpecialKey)

Answer 2

如果您想要维护类似于Linq的语法，则可以使用一种方法来获取所有后代（子代+孩子的子代等）。static class NodeExtensions{&nbsp; &nbsp; public static IEnumerable<Node> Descendants(this Node node)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; return node.Children.Concat(node.Children.SelectMany(n => n.Descendants()));&nbsp; &nbsp; }}然后，可以像其他任何查询一样使用where或first或其他查询该可枚举的对象。

Answer 3

用Linq搜索对象树public static class TreeToEnumerableEx{&nbsp; &nbsp; public static IEnumerable<T> AsDepthFirstEnumerable<T>(this T head, Func<T, IEnumerable<T>> childrenFunc)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; yield return head;&nbsp; &nbsp; &nbsp; &nbsp; foreach (var node in childrenFunc(head))&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; foreach (var child in AsDepthFirstEnumerable(node, childrenFunc))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield return child;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; public static IEnumerable<T> AsBreadthFirstEnumerable<T>(this T head, Func<T, IEnumerable<T>> childrenFunc)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; yield return head;&nbsp; &nbsp; &nbsp; &nbsp; var last = head;&nbsp; &nbsp; &nbsp; &nbsp; foreach (var node in AsBreadthFirstEnumerable(head, childrenFunc))&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; foreach (var child in childrenFunc(node))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield return child;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; last = child;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (last.Equals(node)) yield break;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}