¿Hay un nombre aceptado para este tipo de operación enumerable?

Question

A menudo me resulta necesario atravesar árboles de objetos jerárquicos y realizar operaciones en cada elemento a lo largo del camino. ¿Existe un nombre generalmente aceptado para este tipo de operación en la lista de comprensión vernácula? Lo pregunto porque recuerdo haber aprendido por primera vez acerca del zip function de python antes de que tuviera un equivalente en el framework .net y pensar que tenía un nombre inusual pero apropiado.

Aquí hay un par de métodos generalizados que recurren arriba y abajo de las estructuras de los árboles y producen cada elemento a medida que se encuentran.

public static IEnumerable<T> Ancestors<T>(T source, Func<T, T> selector) 
{ 
    do 
    { 
     yield return source; 
     source = selector(source); 
    } while (!Equals(source, default(T))); 
} 

public static IEnumerable<T> Descendents<T>(T source, 
              Func<T, IEnumerable<T>> selector) 
{ 
    var stack = new Stack<T>(); 
    stack.Push(source); 
    while (stack.Count > 0) 
    { 
     source = stack.Pop(); 
     yield return source; 
     var items = selector(source); 
     if (items != null) 
     { 
      foreach (var item in items) 
      { 
       stack.Push(item); 
      } 
     } 
    } 
} 

Answer 1

Estos son estándar Tree Traversal funciones, también conocido comúnmente como "árbol de pie". Es difícil dar ejemplos de nombres estandarizados porque no se conoce la estrategia concreta de caminar :)

Answer 2

Suponiendo que el selector da los nodos secundarios, el segundo método es el recorrido "primero la primera profundidad derecha". Es decir, si usted tenía

 A 
    /\ 
    B  C 
/\ /\ 
D E F G 

Entonces se obtiene A, C, G, F, B, E, D se obtiene "G" antes de "B", porque "primera profundidad" va tan profundo como pueda antes de probar otra rama. En su ejemplo particular, obtendrá C antes de B porque prioriza de derecha a izquierda.

Si la ha cambiado a

foreach (var item in items.Reverse()) 

continuación, se obtendría un recorrido izquierdo de primera primero en profundidad, que es como la mayoría de la gente piensa en profundidad primera transversal.

Si cambiaste la pila a una cola, se convertiría en un recorrido "ancho primero". A, B, C, D, E, F, G. Haces un "nivel" completo a la vez.

También hay otros recorridos. Observe que las búsquedas de profundidad primero y de ancho tienen la propiedad de que los nodos padre vienen antes de los nodos secundarios. También puede tener recorridos "posteriores al pedido" en los que cada nodo viene después de sus hijos.

Los árboles binarios también tienen un recorrido "inorder". El recorrido por el interior de este árbol es D, B, E, A, F, C, G. Es decir, cada niño de la izquierda se presenta antes que todos sus antepasados, y cada niño de la derecha aparece después de todos sus antepasados. Como ejercicio, ¿puedes escribir un recorrido en orden en un árbol binario?