问如何“展开”“递归”结构

EN

我不相信LINQ里面有什么东西能做到这一点。

像这样递归地这样做有一个问题--你最终会创建大量的迭代器。如果这棵树很深的话，这可能是相当低效的。韦斯·戴尔和埃里克·利珀特都曾在博客上提到过这一点。

您可以通过删除直接递归来消除这种低效率。例如：

public static IEnumerable<T> SelectRecursive<T>(this IEnumerable<T> subjects,
    Func<T, IEnumerable<T>> selector)
{
    if (subjects == null)
    {
        yield break;
    }

    Queue<T> stillToProcess = new Queue<T>(subjects);

    while (stillToProcess.Count > 0)
    {
        T item = stillToProcess.Dequeue();
        yield return item;
        foreach (T child in selector(item))
        {
            stillToProcess.Enqueue(child);
        }
    }
}

这也将改变迭代顺序--它变成广度优先，而不是深度优先；重写它仍然是深度优先--这是很棘手的。我还将其更改为不使用Any() --这个修改后的版本不会对任何序列进行多次评估，这在某些场景中是很方便的。这确实有一个问题，请注意-它将需要更多的内存，因为排队。我们也许可以通过存储迭代器队列而不是条目来缓解这一问题，但我不能马上确定.这肯定会更复杂。

有一点要注意(当我查找博客文章时，ChrisW也注意到了)--如果你的朋友列表中有任何循环(如果A有B，B有A)，那么你就会永远回忆起来。

在我寻找和考虑类似的解决方案时，我发现了这个问题--在我的例子中，为ASP.NET UI控件创建了一个高效的ASP.NET。我所拥有的递归yield是快速的，但我知道这可能会带来额外的成本，因为控制结构越深，所需的时间就越长。现在我知道这是O(n log n)。

这里给出的解决方案提供了一些答案，但正如注释中所讨论的，它确实改变了顺序( OP并不关心这个顺序)。我意识到，为了保持OP给出的顺序和我所需要的顺序，简单的Queue (使用Jon )和Stack都不能工作，因为所有父对象都会先生成，然后再生成子对象(反之亦然)。

为了解决这个问题并保持我意识到的顺序，解决方案只是将Enumerator本身放在一个Stack上。要使用OPs最初的问题，应该如下所示：

public static IEnumerable<T> SelectRecursive<T>(this IEnumerable<T> subjects, Func<T, IEnumerable<T>> selector)
{
    if (subjects == null)
        yield break;

    var stack = new Stack<IEnumerator<T>>();

    stack.Push(subjects.GetEnumerator());

    while (stack.Count > 0)
    {
        var en = stack.Peek();
        if (en.MoveNext())
        {
            var subject = en.Current;
            yield return subject;

            stack.Push(selector(subject).GetEnumerator());
        }
        else 
        {
            stack.Pop().Dispose();
        }
    }
}

我在这里使用stack.Peek来避免将相同的枚举数推回堆栈，因为这可能是更频繁的操作，期望枚举器提供多个项。

这将创建与递归版本相同的枚举数，但可能比将所有主题放在队列或堆栈中并继续添加任何子代主题更少。这是O(n)时间，因为每个枚举数都是独立的(在递归版本中，对一个MoveNext的隐式调用在递归堆栈中的当前深度对子枚举数执行MoveNext )。

以下是一个实现：

• 深度第一次递归选择，
• 不需要对子集合进行双重迭代，
• 不对所选元素使用中间集合，
• 不能处理周期，
• 可以倒着做。 公共静态IEnumerable SelectRecursive( IEnumerable rootItems，Func选择器){返回新的RecursiveEnumerable(rootItems，选择器，假)；}公共静态IEnumerable SelectRecursiveReverse(此IEnumerable rootItems，Func选择器){返回新的RecursiveEnumerable(rootItems，选择器，真)；} class RecursiveEnumerable :RecursiveEnumerable{ public RecursiveEnumerable(，，选择器，bool反向){=；；=反向；}en28#；Func _selector；bool _reverse；public IEnumerator GetEnumerator() {返回新枚举数(This)；} System.Collections.IEnumerator {返回GetEnumerator()；}类枚举器: IEnumerator {公共枚举器(RecursiveEnumerable owner) { _owner = owner；Reset()；} RecursiveEnumerable _owner；T _current；Stack _stack = new Stack()；公共T Current { get {get{ if (_stack == null === _stack.Count == 0)抛出新的InvalidOperationException()；返回_current；}{ _current =默认(T)；if (_stack != null) { while (_stack.Count > 0) { _stack.Pop().Dispose()；} _stack = null；} object System.Collections.IEnumerator.Current { get {返回电流；}公共bool MoveNext() { if (_owner._reverse)返回MoveReverse()；否则返回MoveForward()；}公共bool MoveForward() { //第一次？如果(_stack == null) { // ==堆栈_stack =新的Stack()；//从根项开始} //进程枚举器在堆栈上同时(_stack.Count > 0) { //获取当前的变量se = _stack.Peek()；//下一步请.如果(se.MoveNext()) { //存储它_current = se.Current；//获取子条目var childItems = _owner._selector(_current)；如果(childItems != null) { _stack.Push(childItems.GetEnumerator())；}返回true；} //用枚举数se.Dispose()完成；_stack.Pop()；} //已完成！返回false；}公共bool MoveReverse() { //第一次？如果(_stack == null) { // ==堆栈_stack =新的Stack()；//从根项开始} //进程枚举器在堆栈上同时(_stack.Count > 0) { //获取当前的变量se = _stack.Peek()；//下一步请.if (se.MoveNext()) { // Get子项var childItems = _owner._selector(se.Current)；if (childItems != null) {继续；} // Store it _current = se.Current；返回true；} //用枚举数se.Dispose()完成；_stack.Pop()；如果(_stack.Count > 0) { _current = _stack.Peek().Current；返回true；} //已完成！返回false；}公共void (){ Reset()；}