Comment parcourir une arborescence à l'aide d'un générateur?

Question

J'essaie de comprendre comment implémenter une fonction dans un nœud d'arbre qui renvoie toutes ses feuilles descendantes (qu'elles soient directes ou indirectes). Cependant, je ne souhaite pas transmettre un conteneur dans lequel les nœuds terminaux seront placés de manière récursive (l'arbre pourrait être énorme), mais j'aimerais plutôt utiliser un générateur pour effectuer une itération dans l'arbre. J'ai essayé quelques approches mais aucune d'entre elles n'a encore fonctionné. Celui-ci est le plus proche que je suis venu à une solution possible:

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

Mais cela ne fonctionne pas non plus. Qu'est-ce que je fais mal? On dirait qu’appeler .EnumerateLeaves récursivement ne fonctionnera pas s’il existe une déclaration de rendement dans la même fonction.

Toute aide serait très appréciée. Merci d'avance.

Modifier: j'ai oublié de mentionner qu'une branche peut avoir des feuilles ou des branches enfant, d'où la récursivité.

Answer 1

Voici comment vous devez implémenter 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 a raison - un problème potentiel avec cette méthode, cependant, est que l'appel récursif à des énumérables peut produire des performances de O (n ^ 2). Si cela pose un problème, vous devriez plutôt factoriser la récursivité et utiliser une pile interne.

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

Ceci devrait remplir la même fonction, sans la récursivité.

Modifier: Daniel Plaisted posté dans un commentaire sur un problème plus important lié à l'appel récursif des énumérateurs, résumé dans un publier sur les blogs MSDN concernant les itérateurs . Merci Daniel. =)

Autre édition: N'oubliez jamais que la simplicité du code peut être plus importante que les performances, en particulier si vous attendez des autres utilisateurs qu'ils conservent votre code. Si vous ne vous attendez pas à ce que votre arbre devienne très gros, utilisez la méthode de récursion lassevk décrite dans sa réponse.

Answer 3

Les autres réponses sont correctes, mais le modèle consistant à avoir un rendement dans une boucle foreach avec un appel récursif fera en sorte que le temps d'exécution pour effectuer une itération dans l'arborescence ressemble à O (nombre de nœuds * profondeur moyenne d'un nœud). Voir ce billet de blog pour plus d'informations. détails sur le problème.

Voici une tentative de création d'un générateur efficace en termes d'exécution et d'utilisation de la mémoire:

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

        }
    }

}