如何进行递归的LINQ查询？

Question

我有一个递归的数据结构，例如链表:

class Node
{
    private Node next;
    private int data;

    // (...)
    public Node Next
    {
        get
        {
            return next;
        }
    }

    public int Data
    {
        get
        {
            return data;
        }
    }
}

我想创建一个LINQ查询，从列表头开始遍历元素，并在遍历过程中实时收集数据。如何做到？

- Spook

---

你是否有一个 List<Node>，想要应用 LINQ，或者你只是有一个 Node 实例，该实例在层次结构中包含更多的 Node 类实例，并且你想按顺序从头到尾逐个获取所有对象的数据？ - Nitin Joshi

只有一个 Node。如果我有 List<Node>，我可以简单地使用现有的 LINQ 扩展 :) - Spook

Answer 1

以下是我用来解析TreeView控件中所有节点的两个辅助类。

你可以看到如何使用yield关键字将其调整为符合您需求的方式。

internal static IEnumerable<TreeNode> Descendants(this TreeNodeCollection c)
{
    foreach (var node in c.OfType<TreeNode>())
    {
        yield return node;

        foreach (var child in node.Nodes.Descendants())
        {
            yield return child;
        }
    }
}

例如：

var allCheckedNodes = myTreeView.Nodes.Descendants().Where(c => c.Checked);

- Larry

---

这是一个很酷的解决方案，尽管它是为特定的类创建的，但我更喜欢通用 + lambda 的解决方案，因为它稍微更灵活一些。对于 yield 我给予了极大的赞赏 - 它使我的代码变得更简单了！ - Spook

Answer 2

大概很可能无法使用常规的LINQ扩展来实现，但是可以使用以下扩展方法：

public static IEnumerable<U> For<T, U>(this T obj, Func<T, U> extract, Func<T, bool> continueCondition, Func<T, T> step)
{
    while (!continueCondition(obj))
    {
        yield return extract(obj);
        obj = step(obj);
    }
}

现在，您可以编写酷炫的查询，例如：

head.For(n => n.SomeData, n => n != null, n => n.Next)
    .Select(n => n.Data)
    // More LINQ here

例如，让我们用fancy linq-maniac的方式将1到20之间所有偶数相加。

int sum = 1.For(n => n, n => n <= 20, n => n + 1)
    .Where(n => n % 2 == 0)
    .Aggregate((a, b) => a + b);

- Spook

---

这看起来是MoreLINQ的Generate更复杂的版本。既然LINQ有TakeWhile，因此没有必要使用continueCondition，也不需要extract，因为LINQ有Select。 - Ben Aaronson

@BenAaronson 嗯，除了每次使用TakeWhile时必须记住它之外（尽管我同意不需要extract），由于通常这是最常见的情况，所以我建议保留这个 :) - Spook

是的，通常来说，拥有这个是有意义的。 - Ben Aaronson

Answer 3

仅使用简单的LINQ查询遍历任意复杂的数据结构是很困难的。在某些时候，您需要“减少损失”，自己编写迭代器块 - 可能仅针对难以用标准LINQ表达的部分。

话虽如此，对于您的链表示例，使用moreLinq，您可以执行以下操作：

MoreEnumerable.Generate(head, node => node.Next)
              .TakeWhile(node => node != null)

如果您想进行递归的LINQ树遍历（或类似操作），那么它将会有所不同。以下是一个例子（深度优先）：

private static IEnumerable<Node> GetNodeAndDescendants(Node node)
{
   return new[] { node }.Concat(node.Children.SelectMany(GetNodeAndDescendants));
}

- Ani