Wie durch eine Baumstruktur mit einem Generator wiederholen?

Question

Ich versuche, herauszufinden, wie man eine Funktion in einem Baumknoten zu implementieren, die alle seine Nachkommen Blätter zurück (ob direkt oder indirekt). Aber ich will nicht, um einen Behälter passieren, in dem der Blattknoten rekursiv gesetzt werden (der Baum könnte sehr groß sein), sondern würde Ich mag einen Generator verwenden, durch den Baum zu durchlaufen. Ich habe ein paar Ansätze ausprobiert, aber keiner von ihnen arbeitete bisher. Dieser ist in der Nähe ich auf eine mögliche Lösung gekommen sind:

    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();
            }
        }
    }

Dies ist aber auch nicht arbeiten. Was mache ich falsch? Scheint, wie .EnumerateLeaves rekursiv wird nicht funktionieren, wenn es eine yield-Anweisung in der gleichen Funktion aufrufen.

Jede Hilfe wäre sehr geschätzt. Vielen Dank im Voraus.

Edit:. Ich habe vergessen zu erwähnen, dass ein Zweig entweder Blätter oder Zweige als Kinder hat, damit die Rekursion

Answer 1

Hier ist, wie Sie sollten Branch.EnumerateLeaves implementieren:

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 stimmt - ein potenzielles Problem mit dieser Methode ist jedoch, daß rekursiv Aufruf in enumerables O ergeben kann (n ^ 2) Leistung. Wenn dies ein Problem ist, dann sollten Sie stattdessen die Rekursion aus Faktor und einen internen Stack verwenden.

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]);
            }
        }
    }
}

Dies sollte die gleiche Funktion, ohne die Rekursion durchführen.

Edit: Daniel Plaisted in einem Kommentar über ein größeres Problem mit rekursiven Aufruf Enumeratoren geschrieben, in einem aufsummiert Post auf dem MSDN Blogs in Bezug auf Iteratoren . Dank Daniel. =)

Ein weiterer Edit: Denken Sie immer daran, dass Code Einfachheit als Leistung wichtiger sein kann, vor allem, wenn Sie erwarten, dass andere Ihren Code zu erhalten. Wenn Sie nicht erwarten, dass Ihr Baum sehr groß werden, verwenden Sie die Rekursion Methode lassevk in seiner Antwort skizziert.

Answer 3

Die anderen Antworten sind richtig, aber das Muster innerhalb einer foreach Schleife eine Ausbeute Rückkehr des mit mit einem rekursiven Aufruf wird die Laufzeit macht durch den Baum etwas wie O (Anzahl der Knoten * Durchschnittstiefe eines node) iterieren. Siehe diesem Blog-Eintrag mehr Details über das Problem.

Hier ist ein Versuch, an einem Generator, der sowohl in der Laufzeit und Speichernutzung effizient ist:

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());
                }
            }

        }
    }

}