如何在C#中折叠n-ary树

发布时间：2020-12-15 21:57:53 所属栏目：百科来源：网络整理

导读：我想对n-ary Tree数据结构进行折叠. (fold在 Linq中也称为Aggregate) 我设法找到了一个有效的解决方案： public static R AggregateT,R(T node,FuncT,IEnumerableT getChildren,IEnumerableR,R aggregator){ var childResults = getChildren(node) .Select(c

我想对n-ary Tree数据结构进行折叠. (fold在 Linq中也称为Aggregate)
我设法找到了一个有效的解决方案：

public static R Aggregate<T,R>(T node,Func<T,IEnumerable<T>> getChildren,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#首选.

解决方法

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

public static IEnumerable<T> Traverse<T>(
    this IEnumerable<T> source,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());

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!