Jeneratör kullanarak bir ağaç yapısında yineleme nasıl yapılır?

Question

Bir ağaç düğümündeki tüm işlevlerini (doğrudan veya dolaylı olarak) döndüren bir işlevde nasıl işleneceğini anlamaya çalışıyorum. Bununla birlikte, yaprak düğümlerinin tekrarlı olarak yerleştirileceği bir kaptan (ağaç büyük olabilir) geçmek istemiyorum, bunun yerine ağaç boyunca yinelemek için bir jeneratörü kullanmak istiyorum. Birkaç yaklaşım denedim ama hiçbiri şu ana kadar işe yaramadı. Bu mümkün olan en yakın çözümdür:

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(); 
      } 
     } 
    } 

Fakat bu da çalışmıyor. Neyi yanlış yapıyorum? Aynı işlevde bir getiri ifadesi varsa Yinelenen aramalar gibi görünür.

Herhangi bir yardım çok takdir edilecektir. Şimdiden teşekkürler.

Düzenleme: Bir dalın çocuk olarak yaprak veya dallara sahip olabileceğinden bahsetmeyi unuttum, bu nedenle özyineleme. İşte

Answer 1

Eğer Branch.EnumerateLeaves uygulamalıdır nasıl:

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; 
     } 
    } 
} 

Answer 2

lassevk doğru - o yöntemle bir potansiyel sorun ise yinelemeli enumerable içine çağıran (n^2) performansını O verim olabilir. Bu bir sorunsa, o zaman yinelemeyi dikkate almalı ve bir iç yığını kullanmalısınız.

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]); 
      } 
     } 
    } 
} 

Bu, yineleme olmadan aynı işlevi yerine getirmelidir.

Düzenleme: post on the MSDN Blogs regarding iterators içinde toplanan Enumerators çağrılarak daha büyük bir sorun hakkında bir yorum yayınlanmıştır. Teşekkürler Daniel. =)

Başka Düzenleme: Özellikle kodun diğerlerini beklemesini beklerseniz, bu kod sadeliğinin performanstan daha önemli olabileceğini her zaman unutmayın. Ağacınızın çok büyük büyümesini beklemiyorsanız, cevabında özetlenen özyineleme yöntemini kullanın.

Answer 3

Diğer yanıtlar doğrudur, ancak bir özyinelemeli çağrıyla bir foreach döngüsünün içinde bir döndürme dönüşüne sahip olma modeli, ağaç gibi O (bir düğümün * düğüm sayısı * ortalama sayısı) gibi bir şey yinelemesini sağlar. . Sorun hakkında daha fazla ayrıntı için bkz. 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()); 
       } 
      } 

     } 
    } 

}