代码之家  ›  专栏  ›  技术社区  ›  Andreas Brinck

C#迭代器中的递归

  •  14
  • Andreas Brinck  · 技术社区  · 14 年前

    是否可以在迭代器实现中使用递归 System.Collections.IEnumerable ? 我有一个大致如下声明的树结构:

    public class Node
    {
        public Node Sibling;
        public Node Child;
    }
    

    我想遍历树中的节点。我想做这样的事情(伪代码,我猜不会编译):

    public class NodeIterator : System.Collections.IEnumerable
    {
        Node m_root;
    
        public System.Collections.IEnumerator GetEnumerator()
        {
            recursiveYield(m_root);
        }
    
        System.Collections.IEnumeraton recursiveYield(Node node)
        {
            yield return node;
            if (node.Child)
            {
                recursiveYield(node.Child);
            }
            if (node.Sibling)
            {
                recursiveYield(node.Sibling);
            }
        }
    }
    

    这有可能吗?我知道不用递归就可以用 Node 德克在 GetEnumerator 功能。

    2 回复  |  直到 14 年前
        1
  •  20
  •   John Leidegren    14 年前

    是的,您只需要迭代调用站点的返回值。就像这样:

    IEnumerable<T> Recursive(Node node)
    {
        yield return node;
        foreach (var siblingNode in Recursive(node.Sibling))
        {
            yield return siblingNode;
        }
        foreach (var childNode in Recursive(node.Child))
        {
            yield return childNode;
        }
    }
    

    据记录,这并不比使用队列来实现例如广度优先遍历更好。在最坏的情况下,这样的东西的内存需求是相同的。

        2
  •  3
  •   zero323 little_kid_pea    11 年前

    不,因为 recursiveYield(Node node) 函数将返回一个集合,而您只能生成一个项