एक बयान के साथ एक पेड़ (सूचियों की सूची) flatten?

Question

nHibernate के लिए धन्यवाद, मैं जिन डेटा संरचनाओं के साथ काम करता हूं वे सूचियों के भीतर सूचियों के भीतर सूचियां हैं। तो उदाहरण के लिए मेरे पास "श्रेणी" नामक एक डेटा ऑब्जेक्ट है जिसमें एक है। हल्की संपत्ति जो श्रेणियों की सूची में हल होती है ... जिनमें से प्रत्येक में बच्चे हो सकते हैं ... और इसी तरह से।

मुझे इस संरचना में शीर्ष-स्तरीय श्रेणी में शुरू करने और पूरी संरचना में सभी बच्चों के समान सूची या सरणी या कुछ प्राप्त करने का एक तरीका ढूंढना है - इसलिए सभी बच्चों के सभी बच्चे इत्यादि, एक सूची में चपटा।

मुझे यकीन है कि इसे रिकर्सन के साथ किया जा सकता है, लेकिन मुझे रिकर्सिव कोड को दर्द करने के लिए दर्द मिलता है, और मुझे विश्वास है कि लिंक 4 या किसी भी सुझाव का उपयोग करके नेट 4 में एक और सीधा तरीका होना चाहिए - कोई सुझाव?

Answer 1

अपने श्रेणी वर्ग मान लिया जाये कि तरह दिखता है:

public class Category 
{ 
    public string Name { get; set; } 
    public List<Category> Children { get; set; } 
} 

मैं वहाँ एक "आसान" गैर पुनरावर्ती यह करने के लिए जिस तरह से नहीं लगता कि; यदि आप इसे संभालने के लिए बस एक विधि कॉल की तलाश में हैं, तो "आसान" तरीका रिकर्सिव संस्करण को एक विधि विधि में लिखना है। ऐसा करने के लिए शायद एक पुनरावृत्ति तरीका है, लेकिन मुझे लगता है कि यह वास्तव में बहुत जटिल है। यह कैलकुस का उपयोग किए बिना एक वक्र को टेंगेंट खोजने का "आसान" तरीका पूछने जैसा है।

वैसे भी, यह शायद यह करना होगा:

// Depth-first traversal, recursive 
public static IEnumerable<T> Flatten<T>(
     this IEnumerable<T> source, 
     Func<T, IEnumerable<T>> childrenSelector) 
{ 
    foreach (var item in source) 
    { 
     yield return item; 
     foreach (var child in childrenSelector(item).Flatten(childrenSelector)) 
     { 
      yield return child; 
     } 
    } 
} 

आप इस तरह इसका इस्तेमाल कर सकते हैं::

foreach(var category in categories.Flatten(c => c.Children)) 
{ 
    ... 
} 

public static List<Category> Flatten(Category root) { 

    var flattened = new List<Category> {root}; 

    var children = root.Children; 

    if(children != null) 
    { 
     foreach (var child in children) 
     { 
      flattened.AddRange(Flatten(child)); 
     } 
    } 

    return flattened; 
} 

Answer 2

यहाँ एक विस्तार विधि है कि काम करता है उपरोक्त समाधान गहराई से पहले ट्रैवर्सल करता है, यदि आप एक चौड़ाई-पहले ट्रैवर्सल चाहते हैं तो आप वें कुछ कर सकते हैं है:

// Breadth-first traversal, non-recursive 
public static IEnumerable<T> Flatten2<T>(
     this IEnumerable<T> source, 
     Func<T, IEnumerable<T>> childrenSelector) 
{ 
    var queue = new Queue<T>(source); 
    while (queue.Count > 0) 
    { 
     var item = queue.Dequeue(); 
     yield return item; 
     foreach (var child in childrenSelector(item)) 
     { 
      queue.Enqueue(child); 
     } 
    } 
} 

यह भी गैर पुनरावर्ती होने का लाभ है ...

---

अद्यतन: असल में, मैं सिर्फ एक तरह से गहराई-प्रथम ट्रेवर्सल गैर पुनरावर्ती बनाने के लिए के बारे में सोचा। यहाँ .. यह है:

// Depth-first traversal, non-recursive 
public static IEnumerable<T> Flatten3<T>(
     this IEnumerable<T> source, 
     Func<T, IEnumerable<T>> childrenSelector) 
{ 
    LinkedList<T> list = new LinkedList<T>(source); 
    while (list.Count > 0) 
    { 
     var item = list.First.Value; 
     yield return item; 
     list.RemoveFirst(); 
     var node = list.First; 
     foreach (var child in childrenSelector(item)) 
     { 
      if (node != null) 
       list.AddBefore(node, child); 
      else 
       list.AddLast(child); 
     } 
    } 
} 

मैं उपयोग कर रहा हूँ एक LinkedList<T> क्योंकि सम्मिलन हे हैं (1) के संचालन, जबकि एक List<T> के सम्मिलन हे (एन) कर रहे हैं।

Answer 3

तो चौड़ाई-पहले ट्रेवर्सल ठीक है और आप केवल कुछ कम गैर पुनरावर्ती इनलाइन कोड (3 लाइनों वास्तव में) का उपयोग करना चाहते हैं, अपने मूल तत्व (रों) और उसके बाद के साथ प्रारंभ एक सूची बनाने के लिए सिर्फ एक सरल से यह विस्तार -loop:

// your data object class looks like: 
public class DataObject 
{ 
    public List<DataObject> Children { get; set; } 
    ... 
} 

... 

// given are some root elements 
IEnumerable<DataObject> rootElements = ... 

// initialize the flattened list with the root elements 
var result = new List<DataObject>(rootElements); 
// extend the flattened list by one simple for-loop, 
// please note that result.Count may increase after every iteration! 
for (int index = 0; index < result.Count; index++) 
    result.AddRange(result[index].Children); 

Answer 4

वर्ग @EZHart का उल्लेख है को देखते हुए, आप भी यह इस जो मुझे लगता है कि इस मामले में आसान है के लिए एक सहायक विधि के साथ विस्तार कर सकता है।

public class Category 
{ 
    public string Name { get; set; } 

    public List<Category> Children { get; set; } 

    public IEnumerable<Category> AllChildren() 
    { 
     yield return this; 
     foreach (var child in Children) 
     foreach (var granChild in child.AllChildren()) 
     { 
      yield return granChild; 
     } 
    } 
}