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

Question

Estoy intentando descubrir cómo implementar una función en un nodo de árbol que devuelve todas sus hojas descendientes (ya sean directas o indirectas). Sin embargo, no quiero pasar un contenedor en el que los nodos hoja se colocarán de forma recursiva (el árbol podría ser enorme), en cambio me gustaría utilizar un generador para iterar a través del árbol. He intentado algunos enfoques, pero ninguno de ellos funcionó hasta ahora. Este es el más cercano que he llegado 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 por adelantado.

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

Answer 1

Así es como se 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 es correcto - un problema potencial con este método, sin embargo, es que la llamada recursiva en enumerables puede rendir O (n^2) el rendimiento. Si esto es un problema, entonces debes 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 recurrencia.

Editar: Daniel Plaisted publicado en un comentario sobre un problema mayor con los enumeradores de llamadas recursivas, resumidas en un post on the MSDN Blogs regarding iterators. 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, utilice 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 retorno de rendimiento dentro de un bucle foreach con una llamada recursiva hará que el tiempo de ejecución itere a través del árbol algo así como O (número de nodos * profundidad promedio de un nodo) . Consulte this blog post para obtener más detalles sobre el problema.

Aquí es un intento de un generador que es eficiente, tanto en tiempo de ejecución y el 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()); 
       } 
      } 

     } 
    } 

}