使用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搜索对象树

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

    }
}

Answer 3

如果你想保持Linq之类的语法,你可以使用一个方法来获取所有的后代(儿童+孩子的孩子等)

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

然后可以像使用where或first或者其他任何其他任何其他人一样查询该可枚举.