5

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

    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を再帰的に呼び出すことはできません。

どんな助けでも大歓迎です。前もって感謝します。

編集:ブランチは葉または枝のいずれかを子として持つことができるため、再帰があることを忘れていました。

4

3 に答える 3

7

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;
        }
    }
}
于 2008-12-30T20:40:26.847 に答える
3

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は、再帰的に Enumerators を呼び出すことに関するより大きな問題についてのコメントに投稿し、 iterators に関する MSDN ブログの投稿にまとめました。ありがとうダニエル。=)

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

于 2008-12-30T20:44:33.920 に答える
1

他の答えは正しいですが、再帰呼び出しを使用して 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());
                }
            }

        }
    }

}
于 2008-12-30T21:11:12.493 に答える