这种类型的可枚举操作是否有可接受的名称？

Question

我经常发现自己需要遍历分层对象的树,并在整个过程中对每个项目执行操作.在列表理解白话中,这种操作是否有一个普遍接受的名称？我问,因为我记得首先学习python的zip函数,然后它在.net框架中有一个等价物,并认为它有一个不寻常但恰当的名称.

下面是一些通用的方法,它们可以递增树形结构并在遇到它们时生成每个项目.

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

假设选择器给出子节点,你的第二种方法是"右第一深度优先"遍历.也就是说,如果你有的话

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

然后你得到A,C,G,F,B,E,D.你在"B"之前得到"G",因为"深度优先"在尝试另一个分支之前会尽可能地深入.在您的特定示例中,您将在B之前获得C,因为它优先于左侧.

如果你把它改成了

foreach (var item in items.Reverse())  

然后你会得到一个左先深度优先遍历,这是大多数人对深度优先遍历的看法.

如果您将堆栈更改为队列,那么它将成为"广度优先"遍历.A,B,C,D,E,F,G.你一次做一整个"水平".

还有其他遍历.请注意,深度优先和广度优先搜索都具有父节点位于子节点之前的属性.您还可以进行"后序"遍历,其中每个节点都在其子节点之后.

二叉树也有"顺序"遍历.这棵树的顺序遍历是D,B,E,A,F,C,G.也就是说,每个左边的孩子都来自它的所有祖先,每个正确的孩子都来自它的祖先.作为练习,你能在二叉树上编写有序遍历吗？

Answer 2

这些是标准的树遍历函数，通常也称为“树遍历”。很难给你的例子标准化的名字，因为具体的行走策略是未知的:)