使用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)

{

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

    }

}

例如，使用以下表达式来使用它：

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

Answer 2

如果您想要维护类似于Linq的语法，则可以使用一种方法来获取所有后代（子代+孩子的子代等）。

static class NodeExtensions

{

    public static IEnumerable<Node> Descendants(this Node node)

    {

        return node.Children.Concat(node.Children.SelectMany(n => n.Descendants()));

    }

}

然后，可以像其他任何查询一样使用where或first或其他查询该可枚举的对象。

Answer 3

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

        }

    }

}