अच्छा और सार्वभौमिक रास्ता ट्री

Question

करने के लिए आइटम की सूची कन्वर्ट करने के लिए मैं श्रेणियों की सूची है:

╔════╦═════════════╦═════════════╗ 
║ Id ║ Name  ║ Parent_id ║ 
╠════╬═════════════╬═════════════╣ 
║ 1 ║ Sports  ║ 0   ║ 
║ 2 ║ Balls  ║ 1   ║ 
║ 3 ║ Shoes  ║ 1   ║ 
║ 4 ║ Electronics ║ 0   ║ 
║ 5 ║ Cameras  ║ 4   ║ 
║ 6 ║ Lenses  ║ 5   ║ 
║ 7 ║ Tripod  ║ 5   ║ 
║ 8 ║ Computers ║ 4   ║ 
║ 9 ║ Laptops  ║ 8   ║ 
║ 10 ║ Empty  ║ 0   ║ 
║ -1 ║ Broken  ║ 999   ║ 
╚════╩═════════════╩═════════════╝ 

प्रत्येक श्रेणी के एक माता पिता की है। जब माता-पिता 0 होता है - इसका मतलब है कि यह रूट श्रेणी है।

क्या सबसे अच्छा तरीका है जो इसे नीचे की तरह पेड़ संरचना में परिवर्तित करने के लिए है?

दूसरे शब्दों में - इस संरचना से डेटा लाने के लिए कैसे:

class category 
{ 
    public int Id; 
    public int ParentId; 
    public string Name; 

    public List<Category> Subcategories; 
} 

सार्वभौमिक रास्ते में

:

class category 
{ 
    public int Id; 
    public int ParentId; 
    public string Name; 
} 

इस एक में? // सार्वभौमिक न केवल निर्दिष्ट वर्ग के लिए है।

क्या आपके पास कुछ स्मार्ट विचार हैं? ;)

---

डाटा:

var categories = new List<category>() { 
    new category(1, "Sport", 0), 
    new category(2, "Balls", 1), 
    new category(3, "Shoes", 1), 
    new category(4, "Electronics", 0), 
    new category(5, "Cameras", 4), 
    new category(6, "Lenses", 5), 
    new category(7, "Tripod", 5), 
    new category(8, "Computers", 4), 
    new category(9, "Laptops", 8), 
    new category(10, "Empty", 0), 
    new category(-1, "Broken", 999), 
}; 

Answer 1

आप सार्वभौमिक विधि you''ll एक अतिरिक्त वर्ग की जरूरत करना चाहते हैं:

public class TreeItem<T> 
{ 
    public T Item { get; set; } 
    public IEnumerable<TreeItem<T>> Children { get; set; } 
} 

फिर इस सहायक के साथ उपयोग करें:

internal static class GenericHelpers 
{ 
    /// <summary> 
    /// Generates tree of items from item list 
    /// </summary> 
    /// 
    /// <typeparam name="T">Type of item in collection</typeparam> 
    /// <typeparam name="K">Type of parent_id</typeparam> 
    /// 
    /// <param name="collection">Collection of items</param> 
    /// <param name="id_selector">Function extracting item's id</param> 
    /// <param name="parent_id_selector">Function extracting item's parent_id</param> 
    /// <param name="root_id">Root element id</param> 
    /// 
    /// <returns>Tree of items</returns> 
    public static IEnumerable<TreeItem<T>> GenerateTree<T, K>(
     this IEnumerable<T> collection, 
     Func<T, K> id_selector, 
     Func<T, K> parent_id_selector, 
     K root_id = default(K)) 
    { 
     foreach (var c in collection.Where(c => parent_id_selector(c).Equals(root_id))) 
     { 
      yield return new TreeItem<T> 
      { 
       Item = c, 
       Children = collection.GenerateTree(id_selector, parent_id_selector, id_selector(c)) 
      }; 
     } 
    } 
} 

उपयोग:

var root = categories.GenerateTree(c => c.Id, c => c.ParentId); 

टेस टिंग:

static void Test(IEnumerable<TreeItem<category>> categories, int deep = 0) 
{ 
    foreach (var c in categories) 
    { 
     Console.WriteLine(new String('\t', deep) + c.Item.Name); 
     Test(c.Children, deep + 1); 
    } 
} 
// ... 
Test(root); 

आउटपुट

Sport 
    Balls 
    Shoes 
Electronics 
    Cameras 
     Lenses 
     Tripod 
    Computers 
     Laptops 
Empty 

Answer 2

foreach (var cat in categories) 
{ 
    cat.Subcategories = categories.Where(child => child.ParentId == cat.Id) 
            .ToList(); 
} 

आप O(n*n) जटिलता मिलेगा।

---

अधिक अनुकूलित रास्ता लुक तालिकाओं का उपयोग करने के लिए है:

var childsHash = categories.ToLookup(cat => cat.ParentId); 

foreach (var cat in categories) 
{ 
    cat.Subcategories = childsHash[cat.Id].ToList(); 
} 

जो तुम देता है O(2*n) ≈ O(n)

परिणाम के रूप में, आप अगले संरचना (LINQPad से दिखाया गया है) होगा:

Answer 3

आप अभिभावक-बाल संबंधों के साथ श्रेणियों की सूची प्राप्त करने के लिए नीचे डेटाबेस क्वेरी का उपयोग कर सकते हैं:

WITH tree (categoryId, parentId, level, categoryName, rn) as 
(
    SELECT categoryId, parentid, 0 as level, categoryName, 

     convert(varchar(max),right(row_number() over (order by categoryId),10)) rn 
    FROM Categories 
    WHERE parentid = 0 

    UNION ALL 

    SELECT c2.categoryId, c2.parentid, tree.level + 1, c2.categoryName, 

     rn + '/' + convert(varchar(max),right(row_number() over 
     (order by tree.categoryId),10)) 
    FROM Categories c2 

    INNER JOIN tree ON tree.categoryId = c2.parentid 
) 

SELECT * 
FROM tree 
order by RN 

मुझे आशा है कि यह आपकी मदद करेगा।

Answer 4

यह एक छोटा सा उदाहरण मैं मार पड़ी है। यह सुंदर "जेनेरिक" है।

कोई इंटरफेस को परिभाषित करके एक सामान्य दृष्टिकोण भी बना सकता है (जो फ़ंक्शन तर्कों को सरल बनाने की अनुमति देगा) - हालांकि, मैंने ऐसा नहीं करना चुना। किसी भी मामले में, "मैपर" और चयनकर्ता फ़ंक्शन यह अलग-अलग प्रकारों में काम करने की अनुमति देता है।

भी ध्यान रखें कि इस नहीं एक बहुत ही कुशल कार्यान्वयन है (चूंकि वह सभी subtrees और बार-बार दोहराता इस तरह के लिए सभी संभव बच्चों के आसपास रहता है), लेकिन दिए गए कार्य के लिए उपयुक्त हो सकता है। अतीत में मैंने Dictionary<key,collection> दृष्टिकोण का भी उपयोग किया है, जिसमें बेहतर सीमाएं हैं, लेकिन मुझे इसे इस तरह लिखने की तरह महसूस नहीं हुआ :)

यह "LINQPad C# प्रोग्राम" के रूप में चलता है। का आनंद लें!

// F - flat type 
// H - hiearchial type 
IEnumerable<H> MakeHierarchy<F,H>(
    // Remaining items to process 
    IEnumerable<F> flat, 
    // Current "parent" to look for 
    object parentKey, 
    // Find key for given F-type 
    Func<F,object> key, 
    // Convert between types 
    Func<F,IEnumerable<H>,H> mapper, 
    // Should this be added as immediate child? 
    Func<F,object,bool> isImmediateChild) { 

    var remainder = flat.Where(f => !isImmediateChild(f, parentKey)) 
     .ToList(); 

    return flat 
     .Where(f => isImmediateChild(f, parentKey)) 
     .Select(f => { 
      var children = MakeHierarchy(remainder, key(f), key, mapper, isImmediateChild); 
      return mapper(f, children); 
     }); 
} 

class category1 
{ 
    public int Id; 
    public int ParentId; 
    public string Name; 

    public category1(int id, string name, int parentId) { 
     Id = id; 
     Name = name; 
     ParentId = parentId; 
    } 
}; 

class category2 
{ 
    public int Id; 
    public int ParentId; 
    public string Name; 

    public IEnumerable<category2> Subcategories; 
}; 

List<category1> categories = new List<category1>() { 
    new category1(1, "Sport", 0), 
    new category1(2, "Balls", 1), 
    new category1(3, "Shoes", 1), 
    new category1(4, "Electronics", 0), 
    new category1(5, "Cameras", 4), 
    new category1(6, "Lenses", 5), 
    new category1(7, "Tripod", 5), 
    new category1(8, "Computers", 4), 
    new category1(9, "Laptops", 8), 
    new category1(10, "Empty", 0), 
    new category1(-1, "Broken", 999), 
}; 

object KeyForCategory (category1 c1) { 
    return c1.Id; 
} 

category2 MapCategories (category1 c1, IEnumerable<category2> subs) { 
    return new category2 { 
     Id = c1.Id, 
     Name = c1.Name, 
     ParentId = c1.ParentId, 
     Subcategories = subs, 
    }; 
} 

bool IsImmediateChild (category1 c1, object id) { 
    return c1.ParentId.Equals(id); 
} 

void Main() 
{ 
    var h = MakeHierarchy<category1,category2>(categories, 0, 
     // These make it "Generic". You can use lambdas or whatever; 
     // here I am using method groups. 
     KeyForCategory, MapCategories, IsImmediateChild); 
    h.Dump(); 
} 

Answer 5

इल्या इवानोव एल्गोरिथ्म ( ऊपर देखें) का उपयोग करते हुए, मैं विधि अधिक सामान्य बना दिया।

public static IEnumerable<TJ> GenerateTree<T, TK, TJ>(this IEnumerable<T> items, 
                 Func<T, TK> idSelector, 
                 Func<T, TK> parentSelector, 
                 Func<T, IEnumerable<T>, TJ> outSelector) 
{ 
     IList<T> mlist = items.ToList(); 

     ILookup<TK, T> mcl = mlist.ToLookup(parentSelector); 

     return mlist.Select(cat => outSelector(cat, mcl[idSelector(cat)])); 
} 

उपयोग:

IEnumerable<Category> mlc = GenerateTree(categories, 
             c => c.Id, 
             c => c.ParentId, 
             (c, ci) => new Category 
             { 
               Id = c.Id, 
               Name = c.Name, 
               ParentId = c.ParentId , 
               Subcategories = ci 
             });