4

我想对 n-ary Tree 数据结构进行折叠。（折叠在 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。
定义了如何使用当前节点及其子节点的aggregator结果来处理节点。

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

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

  • 该算法是惰性的，但只是一种。
    例如，如果aggregatoronly 使用Enumerable.First子节点的结果，则只遍历树的最左边的分支。然而，Enumerable.Last整个树被遍历，即使计算只需要最右边的分支。
    我怎样才能让算法真正变得懒惰？

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

4

2 回答 2

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());
于 2013-10-23T16:22:52.833 回答
0

  • 如果要保存堆栈，则在遍历树时会花费内存，而不是深度优先切换到广度优先，或者某些适合您的确切要求的树遍历技术。

  • 至于让它“适当地”变得懒惰，请将您的聚合器从遍历中解开。只需先构建一个惰性遍历（以您想要的任何顺序）并将其传递给您的聚合器。

此外，对于您对懒惰的担忧，您不太确定您的界面选择。Enumerable.First 与 Enumerable.Last 会根据提供者（getChildren）的变化对同一棵树产生不同的结果，那么为什么要考虑懒惰呢？所以我认为排序/遍历方案（即使是深度优先与广度优先）应该是您的聚合器所固有的，或者对于树的类型是固定的？不是外部参数？

于 2013-10-23T15:28:34.763 回答