Is there an accepted name for this type of enumerated operation?

Question

I often have to traverse trees of hierarchical objects and perform operations on each element along the way. Is there a common name for such operations in the concept of a list? I ask because I remember how I first learned about python zip function before he got the equivalent in the .net structure and thought that he had an unusual but suitable name.

Here are a few generalized methods that recurs up and down tree structures and give each element how they meet.

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

Assuming the selector gives the child nodes, your second method is the first "first first step forward." That is, if you have

  A / \ BC / \ / \ DEFG 

Then you get A, C, G, F, B, E, D. You get “G” to “B” because “depth first” goes as deep as possible before it tries to use another branch. In your specific example, you will get C to B because it determines the priorities from right to left.

If you changed it to

 foreach (var item in items.Reverse()) 

then you will get around the first or first depth, as most people think about the first passage of depth.

If you changed the stack to a queue, then it will become a "workaround". A, B, C, D, E, F, G. You complete the whole “level” at a time.

There are other passages. Note that depth and width searches first have the property that the parent nodes belong to child nodes. You can also have "post-order" traversals in which each node appears after its children.

Binary trees also have "in order" traversal. The transverse course of this tree is D, B, E, A, F, C, G. That is, every left child meets all his ancestors, and every right child comes after all his ancestors. As an exercise, can you write a traversal in order on a binary tree?

Answer 2

These are standard features of Tree Traversal , also commonly known as a tree walk. It's hard to call your examples standardized names, because the specific walking strategy is unknown :)