Hoe om Itereer deur 'n boom struktuur met behulp van 'n kragopwekker?

Question

Ek probeer om uit te vind hoe om 'n funksie in 'n boomstruktuur wat al sy afstammeling blare terugkeer (hetsy direk of indirek) te implementeer. Maar ek wil nie 'n houer waarin die Blaarlittetekens rekursief gestel sal word (die boom kan groot wees) slaag, in plaas wil ek graag 'n kragopwekker gebruik om Itereer deur die boom. Ek het probeer om 'n paar benaderings maar nie een van hulle het tot dusver. Hierdie een is die naaste wat ek aan 'n moontlike oplossing het gekom:

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

Maar dit is ook nie werk nie. Wat doen ek verkeerd? Lyk soos 'n beroep .EnumerateLeaves rekursief sal nie werk as daar 'n opbrengs verklaring in dieselfde funksie.

Enige hulp sal baie waardeer word. Dankie by voorbaat.

Edit:. Ek het vergeet om te noem dat 'n tak of blare of takke as kinders kan hê, vandaar die rekursie

Answer 1

Hier is hoe jy Branch.EnumerateLeaves moet implementeer:

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 is reg - een potensiële probleem met hierdie metode is egter dat rekursief roep in enumerables O kan oplewer (n ^ 2) prestasie. As dit is 'n probleem, dan moet jy in plaas faktor die rekursie uit en gebruik 'n interne stapel.

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

Dit moet dieselfde funksie verrig, sonder die rekursie.

Edit: Daniel Plaisted gepos in 'n opmerking oor 'n groter probleem met rekursief roep opnemers, opgesom in 'n post op die MSDN Blogs betrekking tot iterators . Dankie Daniel. =)

Nog 'Edit: Onthou altyd dat kode eenvoud kan belangriker as prestasie, veral as jy ander verwag om jou kode te handhaaf. As jy nie verwag dat jou boom om te groei baie groot, gebruik die rekursie metode lassevk uiteengesit in sy antwoord.

Answer 3

Die ander antwoorde is korrek, maar die patroon van 'n opbrengs terugkeer binne 'n foreach lus met 'n rekursiewe oproep sal die bestuur van tyd tot Itereer deur die boom so iets O maak (aantal nodes * gemiddelde diepte van 'n knoop). Sien hierdie blog post vir meer besonderhede oor die probleem.

Hier is 'n poging om 'n kragopwekker wat doeltreffend in beide runtime en geheue gebruik:

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

        }
    }

}