Czy istnieje akceptowana nazwa dla tego rodzaju operacji przeliczalnych?

Question

Często potrzebuję przechodzić drzewa hierarchicznych obiektów i wykonywać operacje na każdym z elementów po drodze. Czy istnieje ogólna akceptowana nazwa tego rodzaju operacji w języku zrozumiałym dla listy? Pytam, ponieważ pamiętam, że najpierw dowiedziałem się o Pythonie zip function, zanim miał on odpowiednik w strukturze .net i myślał, że ma nietypową, ale odpowiednią nazwę.

Oto kilka ogólnych metod rekurencyjnych w górę i w dół struktur drzewa i przynosi każdy z nich w miarę ich napotykania.

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

Są to standardowe Tree Traversal funkcje, powszechnie znany jako „drzewa chodzenia”. Trudno podać znormalizowane nazwy przykładów, ponieważ konkretna strategia chodzenia nie jest znana :)

Answer 2

Zakładając, że selektor daje węzły potomne, twoja druga metoda to przemiana "pierwsza pierwsza głębia pierwsza". Oznacza to, że jeśli miał

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

następnie dostać A, C, G, F, B, E, D. dostać "G" przed "B", ponieważ "głębokość najpierw" idzie tak głęboko, jak to możliwe zanim spróbuje innej gałęzi. W twoim konkretnym przykładzie dostaniesz C przed B, ponieważ pierwszeństwo ma nad lewicą.

Jeśli zmieniono go

foreach (var item in items.Reverse()) 

następnie chcesz uzyskać lewej pierwszej głębokości pierwszego przechodzenie, który jest jak większość ludzi myśli o głębokości pierwszego przechodzenia.

Po zmianie stosu na kolejkę stanie się to przejściem "od szerokości". A, B, C, D, E, F, G. Robisz cały "poziom" na raz.

Istnieją również inne ruchy. Zauważ, że pierwsze i pierwsze przeszukiwanie mają tę właściwość, że węzły nadrzędne występują przed węzłami potomnymi. Możesz także wykonywać "post-order", w których każdy węzeł przychodzi po swoich dzieciach.

Drzewa binarne również przechodzą "na zamówienie". Przemierzanie tego drzewa to D, B, E, A, F, C, G. Oznacza to, że każde lewe dziecko pojawia się przed wszystkimi jego przodkami, a każde prawe dziecko przychodzi po wszystkich swoich przodkach. Czy jako ćwiczenie możesz napisać sekwencję w kolejności na drzewie binarnym?