कार्यात्मक सी # में एक पेड़ traversing

Question

सी # में निम्नलिखित विस्तार विधि पर विचार करें, Traverse:

IEnumerable<T> Traverse<T>(this IEnumerable<T> source, 
           Func<T, IEnumerable<T>> fnRecurse); 

इस विधि से एक के रूप टी द्वारा परिभाषित किया गया और जो कुछ भी समारोह अपने subnodes वापस जाने के लिए टी का कारण बनता है एक पेड़ के माध्यम से recurse करने की अनुमति देता है।

अब टी के निम्नलिखित कार्यान्वयन पर विचार करें:

class Node 
{ 
    public string Name; 
    public List<Node> Children; 
} 

मेरा लक्ष्य कम से कम समारोह संभव है कि एक IEnumerable लौट इस पेड़ में प्रत्येक नोड के लिए पूरी तरह से योग्य पथ युक्त होगा लिखने के लिए है। कुछ ऐसा:

var node = GetParentNode(); 
return node.Traverse(node => node.Children) 
      .Select(node => GetParentName(node) + ":" + node.Name); 

जाहिर है, नोड को एक मूल संपत्ति जोड़ना समस्या को छोटा बनाता है। इसके बजाय मैं किसी भी तरह एक मजेदार के अंदर अपने माता-पिता तार बनाना चाहता हूं। मुझे नहीं लगता कि यह सी ++ में बहुत कठिन होगा लेकिन मुझे नहीं लगता कि सी # में इसे कैसे किया जाए। कोई विचार?

Answer 1

मुझे लगता है कि चाल बस Node प्रकार को पास नहीं करना है। इसके बजाय Node पास करें और यह योग्य मार्ग है। उदाहरण के लिए

var node = GetTheStartNode(); 
var start = new { Path = node.Name; Node = node }; 
var paths = 
    start 
    .Traverse(x => x.Node.Children.Select(
     c => new { .Path = x.Path + ":" c.Name; .Node=c)) 
    .Select(x => x.Path); 

Answer 2

खैर मुझे नहीं लगता कि आप पेड़ खोज जब तक आप नोड आप एक माता पिता के सूचक के भंडारण के बिना ढूंढ़ रहे हैं, से बचने कर सकते हैं।

आप रूट से शुरू करेंगे। एक मैच के लिए वर्तमान नोड का परीक्षण करें। यदि यह एक मैच है, तो नोड या सिर्फ नाम (इस तत्व की सूची के रूप में) को वापस करें। अन्यथा, अगर यह एक पत्ता नोड है, तो वापस शून्य। यदि कोई पत्ता नहीं है, तो इसके बच्चों को पार करें और यदि बच्चे गैर-शून्य मान वापस करते हैं, तो वर्तमान नोड को अपनी सूची में प्रीपेड करें और उसे वापस करें।

मूल कॉल से लौटने पर, शून्य का मतलब कोई मिलान नहीं मिला है। अन्यथा आपके पास क्रम में नोड्स की सूची होगी।

Answer 3

सबसे स्पष्ट पुन: प्रयोज्य समाधान:

static IEnumerable<IEnumerable<T>> ComputePaths<T>(T Root, Func<T, IEnumerable<T>> Children) { 
    yield return new[] { Root }; 
    foreach (var Child in Children(Root)) 
     foreach (var ChildPath in ComputePaths(Child, Children)) 
      yield return new[] { Root }.Concat(ChildPath);    
} 

जिसके परिणामस्वरूप गणना आसानी से अपने स्ट्रिंग प्रतिनिधित्व के रूप में तब्दील किया जा सकता है:

एक सामान्य विधि है कि सभी संभव pathes विश्लेषण करता है बनाएँ।

// All paths 
    var Paths = ComputePaths(Test, x => x.Children); 

    // Compute string representation 
    var StrPaths = from p in Paths select string.Join(":", p.Select(t => t.Name).ToArray()); 

    foreach(var p in StrPaths) 
     Console.WriteLine(p);