[LINQ].NET/C#应用程序开发中使用LINQ中如何在树中查找满足条件的节点呢？

问题描述

在.NET/C#应用程序开发中，当前有一个树的实体类，如下：

class Node
{
    public string Key { get; }
    public List<Node> Children { get; }
}

现在需要使用LINQ从树的所有节点中查找出所有节点属性Key满足指定条件的节点，比如：

node.Key== SomeSpecialKey

应该如何实现呢？

方案一

解决此类问题有很多种方案，比如我们可以使用递归来处理，也是最简单的实现方式。但我们还可以使用堆栈(stack)或者队列(queue)来处理。比如下面就以一个非递归的实现方式举例，如下：

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)

方案二

此方案为一个树的静态扩展类以及其静态扩展方法实现，可以指定搜索子节点的条件表达式，如下：

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

    }
}

方案三

另一种使用LINQ的SelectMany()方法实现的树节点的查找功能，如下：

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

或者：

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

方案四

一个完整的示例：

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

测试用例：

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