Come scorrere una struttura ad albero usando un generatore?

Question

Sto cercando di capire come implementare una funzione in un nodo dell'albero che restituisce tutte le sue foglie discendenti (dirette o indirette). Tuttavia, non voglio passare un contenitore in cui i nodi foglia verranno inseriti in modo ricorsivo (l'albero potrebbe essere enorme), invece mi piacerebbe usare un generatore per iterare attraverso l'albero. Ho provato alcuni approcci ma nessuno di loro ha funzionato finora. Questo è il più vicino a cui sono arrivato a una possibile soluzione:

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

Ma neanche questo funziona. Che cosa sto facendo di sbagliato? Sembra chiamare .EnumerateLeaves in modo ricorsivo non funzionerà se c'è una dichiarazione di rendimento nella stessa funzione.

Qualsiasi aiuto sarebbe molto apprezzato. Grazie in anticipo.

Modifica: ho dimenticato di dire che un ramo può avere foglie o rami come bambini, da cui la ricorsione.

Answer 1

Ecco come implementare 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 ha ragione: un potenziale problema con quel metodo, tuttavia, è che la chiamata ricorsiva in enumerabili può produrre prestazioni O (n ^ 2). Se questo è un problema, dovresti invece fattorizzare la ricorsione e utilizzare uno stack interno.

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

Questo dovrebbe svolgere la stessa funzione, senza ricorsione.

Modifica: Daniel Plaisted pubblicato in un commento su un problema più grande con gli enumeratori che chiamano ricorsivamente, riassunto in un post sui blog di MSDN relativi agli iteratori . Grazie Daniel. =)

Un'altra modifica: ricorda sempre che la semplicità del codice può essere più importante delle prestazioni, soprattutto se ti aspetti che gli altri mantengano il tuo codice. Se non ti aspetti che il tuo albero cresca molto grande, usa il metodo di ricorsione lassevk delineato nella sua risposta.

Answer 3

Le altre risposte sono corrette, ma lo schema di avere un rendimento in un ciclo foreach con una chiamata ricorsiva renderà il tempo di esecuzione per scorrere attraverso l'albero qualcosa come O (numero di nodi * profondità media di un nodo). Vedi questo post sul blog per ulteriori informazioni dettagli sul problema.

Ecco un tentativo di un generatore che è efficiente sia in runtime che nell'uso della memoria:

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

        }
    }

}