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

我想弄清楚如何在树节点中实现一个函数，该树节点返回其所有后代树叶（不管是直接的还是间接的）。但是，我不想传递一个容器，其中叶节点将递归（树可能很大），而是我想使用生成器遍历树。我尝试了一些方法，但目前为止它们都没有工作。这一个是最接近我已经来到一个可能的解决方案：如何使用生成器遍历树结构？

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

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

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

来源

2008-12-30 Trap

这不是一个.NET的问题吗？ – 2008-12-30 22:07:23

是 - 已被重新标记。编程站点上的“编程”标签是多余的。 =） – 2008-12-30 22:09:20

这里是你应该如何实现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-30 20:40:26

因为一个分支可能会有另一个分支作为子元素，所以这样做不起作用，这就是我使用递归的原因。 – Trap 2008-12-30 20:42:54

让我编辑答案。 – 2008-12-30 20:44:13

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发表在一个关于递归调用统计员的更大问题的评论，总结在post on the MSDN Blogs regarding iterators。谢谢丹尼尔。 =）

另一个编辑：永远记住，代码简洁性可能比性能更重要，特别是如果你期望别人维护你的代码。如果你不希望你的树变得很大，使用他的答案中列出的递归方法lassevk。

来源

2008-12-30 20:44:33

其他答案是正确的，但在递归调用中在foreach循环中产生yield返回的模式将使得遍历树的运行时间类似O（节点数*节点的平均深度）。有关该问题的更多详细信息，请参阅this blog post。

这里是发电机的尝试是在两种运行时和内存使用效率：

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-30 21:11:12

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

回答

相关问题