c# - 这种类型的可枚举操作是否有公认的名称？

Question

我经常发现自己需要遍历分层对象树并沿途对每个项目执行操作。这种操作在列表理解白话里有没有一个普遍接受的名字？我问是因为我记得第一次学习 python 的 zip function早在它在 .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，即每个左 child 都在其所有祖先之前，每个右 child 都在其所有祖先之后。作为练习，你能写一个二叉树的中序遍历吗？