Un modo piacevole e universale per convertire un elenco di elementi in Albero

Ho una lista di categorie:

╔════╦═════════════╦═════════════╗ ║ 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 ║ ╚════╩═════════════╩═════════════╝ 

Ogni categoria ha un genitore. Quando genitore è 0, significa che è la categoria radice.

Qual è il modo migliore per convertirlo in una struttura ad albero come di seguito?

inserisci la descrizione dell'immagine qui

In altre parole: come portare i dati da questa struttura:

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

In questo:

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

in modo universale? // Universal significa non solo per la class citata.

Hai qualche idea intelligente? 😉


Dati:

 var categories = new List() { 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), }; 

Se vuoi avere un metodo universale hai bisogno di una class aggiuntiva:

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

Quindi usalo con questo aiutante:

 internal static class GenericHelpers { ///  /// Generates tree of items from item list ///  /// /// Type of item in collection /// Type of parent_id /// /// Collection of items /// Function extracting item's id /// Function extracting item's parent_id /// Root element id /// /// Tree of items public static IEnumerable> GenerateTree( this IEnumerable collection, Func id_selector, Func 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 { Item = c, Children = collection.GenerateTree(id_selector, parent_id_selector, id_selector(c)) }; } } } 

Uso:

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

test:

 static void Test(IEnumerable> 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); 

Produzione

 Sport Balls Shoes Electronics Cameras Lenses Tripod Computers Laptops Empty 
 foreach (var cat in categories) { cat.Subcategories = categories.Where(child => child.ParentId == cat.Id) .ToList(); } 

Otterrai la complessità di O(n*n) .


Il modo più ottimizzato è utilizzare le tabelle di ricerca:

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

Che ti dà O(2*n)O(n)

Come risultato, avrai la struttura successiva (mostrata da LinqPad):

inserisci la descrizione dell'immagine qui

È ansible utilizzare sotto la query del database per ottenere l’elenco delle categorie con relazioni parent-child:

 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 

Spero che questo ti possa aiutare.

usando l’algoritmo di Ilya Ivanov ( vedi sopra ), ho reso il metodo più generico.

 public static IEnumerable GenerateTree(this IEnumerable items, Func idSelector, Func parentSelector, Func, TJ> outSelector) { IList mlist = items.ToList(); ILookup mcl = mlist.ToLookup(parentSelector); return mlist.Select(cat => outSelector(cat, mcl[idSelector(cat)])); } 

utilizzo:

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

Ecco un piccolo esempio che ho sferrato. È piuttosto “generico”.

Si potrebbe anche fare un approccio generico definendo un’interfaccia (che consentirebbe quindi di semplificare gli argomenti della funzione) – tuttavia, ho scelto di non farlo. In ogni caso, le funzioni “mapper” e selector permettono che funzioni su tipi distinti.

Si noti inoltre che non si tratta di un’implementazione molto efficiente (poiché mantiene attorno a tutti i possibili bambini per tutti i sottoalberi e ripetutamente itera tali), ma potrebbe essere adatta per l’attività specificata. In passato ho anche usato un approccio di Dictionary , che ha dei limiti migliori, ma non avevo voglia di scriverlo in quel modo 🙂

Funziona come un “programma LINQPad C #”. Godere!

 // F - flat type // H - hiearchial type IEnumerable MakeHierarchy( // Remaining items to process IEnumerable flat, // Current "parent" to look for object parentKey, // Find key for given F-type Func key, // Convert between types Func,H> mapper, // Should this be added as immediate child? Func 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 Subcategories; }; List categories = new List() { 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 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(categories, 0, // These make it "Generic". You can use lambdas or whatever; // here I am using method groups. KeyForCategory, MapCategories, IsImmediateChild); h.Dump(); }