जनरेटर का उपयोग कर वृक्ष संरचना के माध्यम से कैसे पुनरावृत्ति करें?

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

लेकिन यह या तो काम नहीं कर रहा। मैं क्या गलत कर रहा हूं? कॉलिंग की तरह लगता है। यदि समान फ़ंक्शन में उपज स्टेटमेंट होता है तो अनन्य रूप से काम नहीं करेगा।

किसी भी मदद की बहुत सराहना की जाएगी। अग्रिम में धन्यवाद।

संपादित करें: मैं एक शाखा या तो पत्ते या बच्चों के रूप में शाखाओं, इसलिए प्रत्यावर्तन हो सकता है उल्लेख करना भूल गया।

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

Answer 2

lassevk सही है - कि विधि के साथ एक संभावित मुद्दा यह है कि रिकर्सिवली enumerables में बुला हे उपज कर सकते हैं (एन^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 का उपयोग करें।

Answer 3

अन्य उत्तरों सही हैं, लेकिन एक पुनरावर्ती कॉल के साथ एक फ़ोरैच लूप के अंदर उपज रिटर्न होने का पैटर्न ओ जैसे पेड़ के माध्यम से फिर से चलने का समय देगा (नोड्स की संख्या * नोड की औसत गहराई) । समस्या के बारे में अधिक जानकारी के लिए 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()); 
       } 
      } 

     } 
    } 

}