如何通过LINQ来展平树？

展平树的问题可以通过以下方法解决：

IEnumerable Flatten(IEnumerable e) =>
    e.SelectMany(c => Flatten(c.Elements)).Concat(new[] { e });

然后可以使用`Where(...)`来根据`group`进行过滤。

为了使代码更加优雅，可以将`Flatten`转换为一个静态类中的扩展函数：

public static IEnumerable Flatten(this IEnumerable e) =>
    e.SelectMany(c => c.Elements.Flatten()).Concat(e);

为了使代码更加优雅，还可以将`Flatten`转换为一个泛型扩展方法，该方法接受一个树和一个从节点生成后代的函数：

public static IEnumerable Flatten(
    this IEnumerable e,
    Func> f
) => e.SelectMany(c => f(c).Flatten(f)).Concat(e);

可以像这样调用这个函数：

IEnumerable tree = ....
var res = tree.Flatten(node => node.Elements);

如果您希望按照前序而不是后序进行展平，可以交换`Concat(...)`中的两个参数位置。

感谢编辑！在调用`Concat`时，元素应为`new[] {e}`，而不是`new[] {c}`（如果使用`c`，甚至无法编译通过）。

我不同意：编译、测试和使用`c`都是可以的。使用`e`编译无法通过。您还可以添加`if (e == null) return Enumerable.Empty();`以处理空子列表。

既然您已经移动了一个括号，那么它就可以编译了 🙂

哦，你是对的，我的括号顺序也错了！

更像是这样：

public static IEnumerable Flatten(this IEnumerable source, Func> f) {
    if (source == null) return Enumerable.Empty();
    return source.SelectMany(c => f(c).Flatten(f)).Concat(source);
}

请注意，此解决方案的时间复杂度为O(nh)，其中n是树中的项数，h是树的平均深度。由于h可以在O(1)和O(n)之间，所以这是一个O(n)到O(n²)的算法。还有更好的算法。

我注意到，如果列表是`IEnumerable`类型，该函数将不会将元素添加到展平列表中。可以通过以下方式调用该函数解决这个问题：

var res = tree.Flatten(node => node.Elements.OfType)

这是正确的，但是如果深度不是问题，这是最可读的解决方案之一。

如何通过LINQ来对树进行扁平化？

有时候我们需要对树形结构进行扁平化处理，将树的节点展开为一个一维集合。这种操作在处理树形数据时非常常见。本文将介绍如何使用LINQ来实现树的扁平化。

首先，我们需要定义一个扩展方法`Flatten`，该方法接受一个泛型参数`T`，并接受一个函数`getChildren`作为参数，用于获取某个节点的子节点。下面是该方法的具体实现：

public static IEnumerable Flatten(
    this IEnumerable items,
    Func> getChildren)
{
    var stack = new Stack();
    foreach(var item in items)
        stack.Push(item);
    while(stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        var children = getChildren(current);
        if (children == null) continue;
        foreach (var child in children) 
            stack.Push(child);
    }
}

这个方法使用了一个堆栈来存储待处理的节点。首先，我们将初始节点添加到堆栈中。然后，进入一个循环，每次从堆栈中弹出一个节点并返回它。接着，我们通过调用`getChildren`函数获取当前节点的子节点，并将它们添加到堆栈中。如果子节点为空，则继续下一次循环。

为了避免可能出现的空引用异常，我们添加了一段代码来检查子节点是否为空，如果不为空则将它们添加到堆栈中：

var children = getChildren(current);
if (children != null)
{
    foreach (var child in children)
        stack.Push(child);
}

此外，我们还需要注意一点，虽然这个方法可以将树扁平化，但是它返回的顺序与原始树的顺序相反。也就是说，最后一个元素会成为第一个元素，以此类推。如果需要按照原始顺序返回结果，可以在调用该方法之后再进行一次反转操作。

最后，我们还需要检查并抛出异常，以防`getChildren`函数为空：

if (getChildren == null)
{
    throw new ArgumentNullException(nameof(getChildren));
}

总结起来，通过使用LINQ的扩展方法`Flatten`，我们可以方便地对树形结构进行扁平化操作。该方法使用堆栈来存储待处理的节点，并通过调用`getChildren`函数来获取子节点。需要注意的是，返回的结果顺序与原始树的顺序相反。如果需要按照原始顺序返回结果，可以在调用该方法之后再进行一次反转操作。另外，我们还需要检查并抛出异常，以防`getChildren`函数为空。

希望本文能够帮助读者理解如何使用LINQ来对树进行扁平化处理。

如何通过LINQ展开树？

通过接受的答案，如果树的深度很大，那么效率就很低。如果树的深度非常大，那么会导致堆栈溢出。可以通过使用显式堆栈来解决这个问题。

public static IEnumerable Traverse(this MyNode root)
{
    var stack = new Stack();
    stack.Push(root);
    while(stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        foreach(var child in current.Elements)
            stack.Push(child);
    }
}

假设树的高度为h，分支因子远小于n，则该方法在堆栈空间上为O(1)，在堆空间上为O(h)，在时间上为O(n)。另一个给出的算法在堆栈上为O(h)，在堆空间上为O(1)，在时间上为O(nh)。如果分支因子与n相比较小，则h介于O(lg n)和O(n)之间，这说明如果h接近n，则简单算法可能使用危险的大量堆栈和大量时间。

现在我们有了遍历，查询就很简单了：

root.Traverse().Where(item=>item.group == 1);

如果你要争论一点的话，也许代码不是显然正确的。有什么可以使它更清楚正确的呢？

首先，我没有看到它如何穿过第一层；递归的缺失使我困惑。显然，这就是它高效的原因。我只是没有正确地阅读它。其次，`Traverse`是对`MyNode`的扩展，而不是对`IEnumerable`的扩展——原始问题没有一个根节点可以调用它。将解决方案更改为`IEnumerable`的通用方法有点尴尬。我通过使用可枚举的初始化`Stack`来完成，但这会提前枚举整个树的顶层。

如何使用`IEnumerable`而不是`root`来使用这个函数呢？

通常你对`IEnumerable`做什么？

循环遍历它！在我的情况下，我有一棵树，可能有多个根节点。所以如果我理解你的代码，我需要对每个根节点调用`Traverse`，对吗？

正确。你可以对所有的元素调用`Traverse`。或者你可以修改`Traverse`，使其接受一个序列，并将序列的所有元素推入`stack`。记住，`stack`是“我还没有遍历的元素”。或者你可以创建一个“虚拟”根节点，其中你的序列是其子节点，然后遍历虚拟根节点。

如果你使用`foreach (var child in current.Elements.Reverse())`，你将得到一个更符合预期的展开顺序。特别是，子节点将按照它们出现的顺序出现，而不是最后一个子节点先出现。在大多数情况下，这应该没有关系，但在我的情况下，我需要展开的顺序是可预测和期望的。

你可以通过用`Queue`替换`Stack`来避免使用`Reverse`。

关于顺序，你是正确的，但是`Reverse`的问题在于它会创建额外的迭代器，而这种方法的目的是避免这种情况。用`Queue`替换`Stack`会得到广度优先遍历。

我是否正确地认为这个功能（非二次递归迭代器）是对你答案的有效替代品？

是的，那个建议的功能在F#中是存在的（作为一个最令人兴奋的功能），并且在一个名为C-Omega的C#研究版本中也有，所以我们知道它是可行的。（尽管我记得听说C-Omega版本的正确性在保持异常行为方面存在问题，我不记得细节了。）

为什么将其命名为`Traverse`而不是`Flatten`树？

我希望强调这是一种延迟遍历；更好的是一些关于遍历类型的指示。我真的应该将其命名为`DepthFirstTraversal`。

参考：[stackoverflow.com/a/73486312/659190](https://stackoverflow.com/a/73486312/659190)，以备重用。