5

我试图弄清楚如何在树节点中实现一个函数，该函数返回其所有后代叶子（无论是直接的还是间接的）。但是，我不想传递将递归放置叶节点的容器（树可能很大），而是我想使用生成器来遍历树。我尝试了几种方法，但到目前为止没有一种方法有效。这是我最接近可能的解决方案的一个：

    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 将不起作用。

任何帮助将不胜感激。提前致谢。

编辑：我忘了提到一个分支可以有叶子或分支作为孩子，因此递归。

4

3 回答 3

7

下面是你应该如何实现 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;
        }
    }
}
于 2008-12-30T20:40:26.847 回答
3

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 博客上关于迭代器的帖子中。谢谢丹尼尔。=)

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

于 2008-12-30T20:44:33.920 回答
1

其他答案是正确的，但是通过递归调用在 foreach 循环内返回 yield 的模式将使遍历树的运行时间类似于 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());
                }
            }

        }
    }

}
于 2008-12-30T21:11:12.493 回答