¿Cómo iterar a través de una estructura de árbol usando un generador?

Question

Estoy tratando de averiguar cómo implementar una función en un nodo de árbol que devuelve todas sus hojas descendientes (directas o indirectas). Sin embargo, no quiero pasar un contenedor en el que los nodos de las hojas se colocarán de forma recursiva (el árbol podría ser enorme), en cambio me gustaría usar un generador para recorrer el árbol. He intentado algunos enfoques pero ninguno de ellos funcionó hasta ahora. Esta es la más cercana que he encontrado a una posible solución:

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

Pero esto tampoco está funcionando. ¿Qué estoy haciendo mal? Parece que llamar .EnumerateLeaves recursivamente no funcionará si hay una declaración de rendimiento en la misma función.

Cualquier ayuda sería muy apreciada. Gracias de antemano.

Editar: olvidé mencionar que una rama puede tener hojas o ramas cuando son niños, de ahí la recursión.

Answer 1

Aquí se explica cómo debe implementar 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 tiene razón: un problema potencial con ese método, sin embargo, es que las llamadas recursivas a los enumerables pueden producir un rendimiento O (n ^ 2). Si esto es un problema, entonces deberías factorizar la recursión y usar una pila interna.

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

Esto debería realizar la misma función, sin la recursión.

Edite: Daniel Plaisted publicado en un comentario sobre un problema mayor al llamar recursivamente a Enumerators, resumido en un publique en los blogs de MSDN sobre iteradores . Gracias daniel =)

Otra edición: recuerde siempre que la simplicidad del código puede ser más importante que el rendimiento, especialmente si espera que otros mantengan su código. Si no espera que su árbol crezca demasiado, use el método de recursión lassevk que se describe en su respuesta.

Answer 3

Las otras respuestas son correctas, pero el patrón de tener un rendimiento dentro de un bucle foreach con una llamada recursiva hará que el tiempo de ejecución para iterar a través del árbol sea algo como O (número de nodos * profundidad promedio de un nodo). Consulte esta publicación de blog para obtener más información detalles sobre el problema.

Este es un intento de un generador que es eficiente tanto en tiempo de ejecución como en uso de 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());
                }
            }

        }
    }

}