如何在C中折叠n元树＃

我想对n元树数据结构进行折叠。（倍是又名聚集在LINQ）
我设法拿出一个工作液：如何在C中折叠n元树＃

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是定义如何让一个给定节点的孩子FUNC。它必须为叶节点返回一个空的IEnumerable。
aggregator定义了如何使用当前节点及其子节点的结果来处理节点。

的解决方案似乎工作，但也存在一些问题：

的算法是递归的，它会吹栈对于很深的树。
如何重写函数以防止堆栈溢出？
该算法是懒惰的，但只有一种。
例如如果aggregator仅使用子节点的Enumerable.First结果，则只遍历树的最左侧分支。然而，与Enumerable.Last整个树被遍历，即使只需要最右边的分支进行计算。
我该如何让算法真的很懒惰？

F＃解决方案欢迎，但C＃首选。

来源

2013-10-23 3dGrabber

当你最初建的树，你不是有一个深筹码？那么为什么当这个算法在构建树的时候已经有了n-deep的堆栈的时候，这个算法会打碎堆栈呢？ – philologon

@philologon：整个树不一定在内存中。一个例子就是一个网络爬虫。 – 3dGrabber

使用延续或蹦床。 –

你穿越树林的时候，如果你想保存在堆栈，而不是深度第一开关先广度，还是有些树遍历技术适合您的具体要求有支出的记忆。至于使其“正常”懒惰，请从遍历中解开聚合器。只要先建立一个懒惰的遍历（以你想要的任何顺序）并将它传递给你的聚合器。

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

来源

2013-10-23 15:28:34 Vivek

您可以使用一个明确的堆栈，而不是递归，以避免消耗堆栈空间遍历树：

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-23 16:22:52 Servy

问题是关于折叠（又名聚合，减少）不遍历。 – 3dGrabber

@ 3dGrabber一旦你有一个扁平化的项目序列，你可以在该序列上使用LINQ'Aggregate'。 – Servy

不是。这会将树变成列表，并折叠列表。结果（通常）不一样。请参阅要求：聚合器定义了如何使用当前节点及其子节点的结果来处理节点**。 – 3dGrabber

如何在C中折叠n元树＃

回答

相关问题