c# - 如何在C#中折叠一棵n叉树

Question

我想对 n 元树数据结构进行折叠。 (折叠在 Linq 中又称为聚合)
我设法想出了一个可行的解决方案:

public static R Aggregate<T, R>(T node,
          Func<T, IEnumerable<T>> getChildren,
       Func<T, IEnumerable<R>, R> aggregator)
{
    var childResults = getChildren(node)
                      .Select(c => Aggregate(c, getChildren, aggregator));

    return aggregator(node, childResults);
}

getChildren 是定义如何获取给定节点的子节点的函数。它必须为叶节点返回一个空的 IEnumerable。
聚合器 定义了如何使用当前节点及其子节点的结果来处理节点。

该解决方案似乎有效但存在一些问题:

• 算法是递归的，它会炸毁深树的堆栈。
  如何重写函数以防止堆栈溢出？

• 算法是惰性的，但只是有点。
  例如如果聚合器只使用子节点的Enumerable.First结果，则只遍历树的最左边的分支。然而，对于 Enumerable.Last，整个树都会被遍历，即使计算只需要最右边的分支。
  如何让算法真正懒惰？

欢迎使用 F# 解决方案，但首选 C#。

Answer 1

您可以使用显式堆栈而不是递归来遍历树，以避免消耗堆栈空间:

public static IEnumerable<T> Traverse<T>(
    this IEnumerable<T> source
    , Func<T, IEnumerable<T>> childrenSelector)
{
    var stack = new Stack<T>(source);
    while (stack.Any())
    {
        var next = stack.Pop();
        yield return next;
        foreach (var child in childrenSelector(next))
            stack.Push(child);
    }
}

如果你想“向后”遍历，你可以在调用它时简单地调整子选择器，而不是调用 Last 而不是 First:

Traverse(root, node => nodes.Reverse());