23

当您想要递归枚举分层对象，根据某些标准选择一些元素时，有许多技术示例，例如“展平”，然后使用 Linq 进行过滤：就像在此处找到的那样：

链接文本

但是，当您枚举诸如 Form 的 Controls 集合或 TreeView 的 Nodes 集合之类的东西时，我无法使用这些类型的技术，因为它们似乎需要一个 IEnumerable 参数（扩展方法） collection : 传入 SomeForm.Controls 不会编译。

我发现最有用的是：

链接文本

这确实为您提供了 Control.ControlCollection 的扩展方法，其结果为 IEnumerable，然后您可以将其与 Linq 一起使用。

我已经修改了上面的示例以毫无问题地解析 TreeView 的节点。

public static IEnumerable<TreeNode> GetNodesRecursively(this TreeNodeCollection nodeCollection)
{
    foreach (TreeNode theNode in nodeCollection)
    {
        yield return theNode;

        if (theNode.Nodes.Count > 0)
        {
            foreach (TreeNode subNode in theNode.Nodes.GetNodesRecursively())
            {
                yield return subNode;
            }
        }
    }
}

这是我现在使用扩展方法编写的那种代码：

    var theNodes = treeView1.Nodes.GetNodesRecursively();

    var filteredNodes = 
    (
        from n in theNodes
            where n.Text.Contains("1")
                select n
    ).ToList();

而且我认为在传入约束的情况下，可能有一种更优雅的方式来做到这一点。

我想知道是否可以通用地定义这样的过程，以便：在运行时我可以将集合的类型以及实际集合传递给通用参数，因此代码与是否它是 TreeNodeCollection 或 Controls.Collection。

我也很想知道是否有任何其他方式（更便宜？更快？）而不是第二个链接（上面）中显示的方式来获取 Linq 可用的形式的 TreeNodeCollection 或 Control.ControlCollection。

Leppie 在链接到第一个（上图）的 SO 帖子中关于“SelectMany”的评论似乎是一个线索。

我对 SelectMany 的实验是：好吧，称它们为“灾难”。:)

感谢任何指针。我花了几个小时阅读我能找到的所有涉及这些领域的 SO 帖子，并漫无目的地进入“y-combinator”这样的异国情调。一个“谦卑”的经历，我可能会补充：）

4

5 回答 5

33

这段代码应该可以解决问题

public static class Extensions
{
    public static IEnumerable<T> GetRecursively<T>(this IEnumerable collection,
        Func<T, IEnumerable> selector)
    {
        foreach (var item in collection.OfType<T>())
        {
            yield return item;

            IEnumerable<T> children = selector(item).GetRecursively(selector);
            foreach (var child in children)
            {
                yield return child;
            }
        }
    }
}

这是一个如何使用它的例子

TreeView view = new TreeView();

// ...

IEnumerable<TreeNode> nodes = view.Nodes.
    .GetRecursively<TreeNode>(item => item.Nodes);

更新：回应 Eric Lippert 的帖子。

这是一个使用All About Iterators中讨论的技术的改进版本。

public static class Extensions
{
    public static IEnumerable<T> GetItems<T>(this IEnumerable collection,
        Func<T, IEnumerable> selector)
    {
        Stack<IEnumerable<T>> stack = new Stack<IEnumerable<T>>();
        stack.Push(collection.OfType<T>());

        while (stack.Count > 0)
        {
            IEnumerable<T> items = stack.Pop();
            foreach (var item in items)
            {
                yield return item;

                IEnumerable<T> children = selector(item).OfType<T>();
                stack.Push(children);
            }
        }
    }
}

我使用以下基准测试技术做了一个简单的性能测试。结果不言自明。树的深度对第二种解决方案的性能只有边际影响；而第一个解决方案的性能迅速下降，最终StackOverflowException导致树的深度变得太大。

基准测试

于 2009-11-29T13:56:31.530 回答
22

您似乎走在正确的轨道上，上面的答案有一些好主意。但我注意到所有这些递归解决方案都有一些严重的缺陷。

假设有问题的树总共有 n 个节点，最大树深度为 d <= n。

首先，它们在树的深处消耗系统堆栈空间。如果树结构非常深，那么这可能会破坏堆栈并使程序崩溃。树深度 d 为 O(lg n)，取决于树的分支因子。更糟糕的情况是根本没有分支——只是一个链表——在这种情况下，只有几百个节点的树会破坏堆栈。

其次，您在这里所做的是构建一个迭代器，该迭代器调用一个迭代器，该迭代器调用一个迭代器......这样顶部迭代器上的每个 MoveNext() 实际上都会执行一系列调用，成本也是 O(d)。如果你在每个节点上都这样做，那么调用的总成本是 O(nd)，这是最坏情况 O(n^2) 和最好情况 O(n lg n)。你可以做得比两者都好；没有理由不能及时线性化。

诀窍是停止使用小而脆弱的系统堆栈来跟踪下一步要做什么，并开始使用堆分配堆栈来显式跟踪。

您应该将 Wes Dyer 关于此的文章添加到您的阅读列表中：

https://blogs.msdn.microsoft.com/wesdyer/2007/03/23/all-about-iterators/

他在最后给出了一些编写递归迭代器的好技巧。

于 2009-11-29T15:46:11.113 回答
2

我不确定 TreeNodes，但您可以使用 IEnumerable 来制作表单的 Controls 集合System.Linq，例如

var ts = (from t in this.Controls.OfType<TextBox>
                 where t.Name.Contains("fish")
                 select t);
//Will get all the textboxes whose Names contain "fish"

很抱歉，我不知道如何使这个递归脱离我的头顶。

于 2009-11-29T13:32:58.667 回答
2

基于 mrydengren 的解决方案：

public static IEnumerable<T> GetRecursively<T>(this IEnumerable collection,
    Func<T, IEnumerable> selector,
    Func<T, bool> predicate)
{
    foreach (var item in collection.OfType<T>())
    {
        if(!predicate(item)) continue;

        yield return item;

        IEnumerable<T> children = selector(item).GetRecursively(selector, predicate);
        foreach (var child in children)
        {
            yield return child;
        }
    }
}


var theNodes = treeView1.Nodes.GetRecursively<TreeNode>(
    x => x.Nodes,
    n => n.Text.Contains("1")).ToList();

编辑：对于 BillW

于 2009-11-29T14:29:55.587 回答
1

我猜你要的是这样的东西。

public static IEnumerable<T> <T,TCollection> GetNodesRecursively(this TCollection nodeCollection, Func<T, TCollection> getSub)
 where T, TCollection: IEnumerable
{   
    foreach (var theNode in )
    {
        yield return theNode;
        foreach (var subNode in GetNodesRecursively(theNode, getSub))
        {
            yield return subNode;
        }
    }
}

var all_control = GetNodesRecursively(control, c=>c.Controls).ToList();
于 2009-11-29T14:06:32.433 回答