ジェネレーターを使用してツリー構造を反復処理する方法は？

Question

すべての子孫の葉を返す（直接または間接）ツリーノードで関数を実装する方法を見つけようとしています。ただし、リーフノードが再帰的に配置されるコンテナ（ツリーは巨大になる可能性があります）を渡したくありません。代わりに、ジェネレータを使用してツリーを反復処理します。私はいくつかのアプローチを試しましたが、それらのどれも今のところ機能しませんでした。これは、可能な解決策に最も近いものです。

    public interface ITreeNode
    {
        IEnumerable<ITreeNode> EnumerateLeaves();            
    }

    class Leaf : ITreeNode
    {
        public IEnumerable<ITreeNode> EnumerateLeaves()
        {
            throw new NotImplementedException();
        }
    }

    class Branch : ITreeNode
    {
        private List<ITreeNode> m_treeNodes = new List<ITreeNode>();

        public IEnumerable<ITreeNode> EnumerateLeaves()
        {
            foreach( var node in m_treeNodes )
            {
                if( node is Leaf )
                    yield return node;
                else
                    node.EnumerateLeaves();
            }
        }
    }

しかし、これも機能していません。何が間違っていますか？同じ関数にyieldステートメントがある場合、.EnumerateLeavesを再帰的に呼び出すことは機能しないようです。

ご協力いただければ幸いです。事前に感謝します。

編集：ブランチがリーフまたはブランチを子として持つ可能性があることを忘れていたため、再帰です。

Answer 1

Branch.EnumerateLeavesの実装方法は次のとおりです。

public IEnumerable<ITreeNode> EnumerateLeaves()
{
    foreach( var node in m_treeNodes )
    {
        if( node is Leaf )
            yield return node;
        else
        {
            foreach (ITreeNode childNode in node.EnumerateLeaves())
                yield return childNode;
        }
    }
}

Answer 2

lassevkは正しいです-ただし、このメソッドの潜在的な問題の1つは、列挙型を再帰的に呼び出すとO（n ^ 2）パフォーマンスが得られることです。これが問題になる場合は、代わりに再帰を除外して内部スタックを使用する必要があります。

public IEnumerable<ITreeNode> EnumerateLeaves()
{
    Stack<ITreeNode> workStack = new Stack<ITreeNode>(m_treeNodes);

    while(workStack.Count > 0) {
        var current = workStack.Pop();
        if(current is Leaf)
            yield return current;
        else {
            for(n = 0; n < current.m_treeNodes.Count; n++) {
                workStack.Push(current.m_treeNodes[n]);
            }
        }
    }
}

これは、再帰なしで同じ機能を実行する必要があります。

編集： Daniel Plaisted は、列挙子を再帰的に呼び出すことに関する大きな問題についてのコメントに投稿しました。 イテレータに関するMSDNブログに投稿。ダニエルに感謝します。 =）

別の編集：特に他の人があなたのコードを維持することを期待する場合、コードの単純さはパフォーマンスよりも重要になる可能性があることを常に覚えておいてください。ツリーが非常に大きくなるとは思わない場合は、彼の答えで概説されている再帰メソッドlassevkを使用してください。

Answer 3

他の答えは正しいですが、再帰呼び出しでforeachループ内にyieldリターンを持たせるパターンにより、実行時間はO（ノード数*ノードの平均深さ）のようにツリーを反復します。詳細については、このブログ投稿をご覧ください。問題の詳細。

実行時とメモリ使用の両方で効率的なジェネレーターの試みは次のとおりです。

class Node
{
    List<Node> _children;

    public bool IsLeaf { get { return _children.Count == 0; } }

    public IEnumerable<Node> Children { get { return _children; } }

    public IEnumerable<Node> EnumerateLeaves()
    {
        if (IsLeaf)
        {
            yield return this;
            yield break;
        }

        var path = new Stack<IEnumerator<Node>>();

        path.Push(Children.GetEnumerator());

        while(!path.Empty)
        {
            var cur = path.Pop();
            if (cur.MoveNext())
            {
                path.Push(cur);
                if (cur.IsLeaf)
                {
                    yield return cur;
                }
                else
                {
                    path.Push(cur.Children.GetEnumerator());
                }
            }

        }
    }

}