c# - 嵌套产量在树中的表现

Question

我有一个树状结构。此结构中的每个元素都应该能够返回它作为根的所有元素的 Enumerable。我们称这个方法为IEnumerable<Foo> GetAll() .所以如果我们有

     A  <-- topmost root
    / \ 
   /   \
  B     C
 / \   / \
D   E F   G

调用GetAll在元素上 C返回 {C, F, G} (元素的固定顺序会很好，但不是必需的)。我想每个人都已经知道了。

当前执行 GetAll看起来像这样:

public IEnumerable<Foo> GetAll ()
{
    yield return this;

    foreach (Foo foo in MyChildren) {
        foreach (Foo f in foo.GetAll ()) {
            yield return f;
        }
    }
}

在早期的实现中，我返回了一个 List 并使用 List.AddRange() 添加了 child-foos .

我的问题是使用 yield 的版本是否正确实现或者是否应该改进(尤其是在性能方面)。或者这只是不好，我应该坚持 List s(或 ReadOnlyCollections)代替？

Answer 1

如果将递归展开到堆栈，您可以提高性能，因此您将只有一个迭代器:

public IEnumerable<Foo> GetAll()
{
    Stack<Foo> FooStack = new Stack<Foo>();
    FooStack.Push(this);

    while (FooStack.Count > 0)
    {
        Foo Result = FooStack.Pop();
        yield return Result;
        foreach (Foo NextFoo in Result.MyChildren)
            FooStack.Push(NextFoo);
    }
}