4

n-ary Tree データ構造をフォールドしたいと思います。（折り畳みはLinqのAggregateとも呼ばれます）
私はなんとか実用的な解決策を思いつきました：

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# を優先します。

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 に答える