如何使用生成器迭代遍历树形结构？

Question

我正在尝试实现一个函数，它可以返回一个节点的所有后代叶子节点（无论是直接还是间接的）。但是，我不想递归地传递一个容器来存放叶子节点（树可能非常大），相反，我想使用生成器来遍历树。我已经尝试了几种方法，但迄今为止都没有成功。这个方法是我最接近可能解决问题的方法：

    public interface ITreeNode
    {
        IEnumerable<ITreeNode> EnumerateLeaves();            
    }

    class Leaf : ITreeNode
    {
        public IEnumerable<ITreeNode> EnumerateLeaves()
        {
            throw new NotImplementedException();
        }
    }

    class Branch : ITreeNode
    {
        private List<ITreeNode> m_treeNodes = new List<ITreeNode>();

        public IEnumerable<ITreeNode> EnumerateLeaves()
        {
            foreach( var node in m_treeNodes )
            {
                if( node is Leaf )
                    yield return node;
                else
                    node.EnumerateLeaves();
            }
        }
    }

但这个也行不通。我做错了什么？如果在同一个函数中有yield语句，貌似递归调用.EnumerateLeaves也不起作用。

非常感谢任何帮助。提前致谢。

编辑：我忘记提到一个分支可以有叶子或分支作为子元素，因此需要递归。

- Trap

---

是的 - 已重新标记。在编程网站上，“编程”标签是多余的。=) - Erik Forbes

Answer 1

以下是如何实现Branch.EnumerateLeaves：

public IEnumerable<ITreeNode> EnumerateLeaves()
{
    foreach( var node in m_treeNodes )
    {
        if( node is Leaf )
            yield return node;
        else
        {
            foreach (ITreeNode childNode in node.EnumerateLeaves())
                yield return childNode;
        }
    }
}

- lassevk

---

好了，这样就可以了，现在它会正确地使用递归。 - Lasse V. Karlsen

那么这将是对树进行O(n log n)次迭代？ - Jules

请参考Erik的答案了解有关性能的更多信息。一如既往，对代码进行分析，如果它是瓶颈，请进行重构。 - Lasse V. Karlsen

我读了这个链接。它的时间复杂度是O(n log n)。这是因为遍历树的递归深度是log n，而不是n。 - recursive

这取决于n是什么以及你的树有多平衡 :) 如果你的树很深但不宽，那么它将更接近O（n ^ 2），其中n是树中节点的数量。 - Daniel Plaisted

Answer 2

lassevk是正确的——然而，使用递归调用枚举可能会导致O(n^2)的性能问题。如果这是一个问题，那么你应该将递归因子分离出来并使用内部堆栈。

public IEnumerable<ITreeNode> EnumerateLeaves()
{
    Stack<ITreeNode> workStack = new Stack<ITreeNode>(m_treeNodes);

    while(workStack.Count > 0) {
        var current = workStack.Pop();
        if(current is Leaf)
            yield return current;
        else {
            for(n = 0; n < current.m_treeNodes.Count; n++) {
                workStack.Push(current.m_treeNodes[n]);
            }
        }
    }
}

这应该执行相同的功能，但不使用递归。

编辑：Daniel Plaisted 在评论中提到了一个更大的问题，即递归调用枚举器，在MSDN博客关于迭代器的文章中总结了这个问题。感谢Daniel. =)

另一个编辑：永远记住，代码简单性可能比性能更重要，特别是如果您希望其他人维护您的代码。如果您不希望树增长得非常大，请使用lassevk在他的回答中概述的递归方法。

- Erik

---

垃圾回收并不是递归中最大的问题，而是每次迭代都必须从顶部向下遍历枚举器的“树”这一事实。这可能会显著增加运行时间。请参阅http://blogs.msdn.com/wesdyer/archive/2007/03/23/all-about-iterators.aspx - Daniel Plaisted

非常正确 - 尽管我无法想出如何措辞。感谢链接 - 非常有帮助。=） - Erik Forbes

Answer 3

其他答案都是正确的，但是在foreach循环中使用yield return和递归调用的模式将使得遍历树的运行时间变为O（节点数*平均深度）。请参见这篇博客文章以获取有关该问题的更多详细信息。

以下是一种既能够高效运行又能够节省内存的生成器尝试：

class Node
{
    List<Node> _children;

    public bool IsLeaf { get { return _children.Count == 0; } }

    public IEnumerable<Node> Children { get { return _children; } }

    public IEnumerable<Node> EnumerateLeaves()
    {
        if (IsLeaf)
        {
            yield return this;
            yield break;
        }

        var path = new Stack<IEnumerator<Node>>();

        path.Push(Children.GetEnumerator());

        while(!path.Empty)
        {
            var cur = path.Pop();
            if (cur.MoveNext())
            {
                path.Push(cur);
                if (cur.IsLeaf)
                {
                    yield return cur;
                }
                else
                {
                    path.Push(cur.Children.GetEnumerator());
                }
            }

        }
    }

}

- Daniel Plaisted

---

你能解释一下这个比O(n^2)更好的地方在哪里吗？我没有看出来。 - Erik Forbes

它的时间复杂度为O(n log n)。在您提供的链接中，递归深度为n。在树中，在平均情况下，它是log n。 - recursive

我更新了它，说明递归方法的运行时间为O(节点数*节点平均深度)。这个应该只需要O(节点数)的运行时间，与Erik的相同。理论上，这个方法使用的内存更少。 - Daniel Plaisted