Хороший и универсальный способ преобразования списка элементов в дерево

У меня есть список категорий:

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

Каждая категория имеет родителя. Когда parent равно 0, это означает, что это корневая категория.

Какой самый лучший способ преобразовать его в древовидную структуру, как показано ниже?

введите описание изображения здесь

Другими словами – как переносить данные из этой структуры:

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

В этом:

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

универсальным способом? // Универсальный означает не только для указанного classа.

У вас есть умные идеи? 😉


Данные:

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

Если вы хотите иметь универсальный метод, вам понадобится дополнительный class:

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

Затем используйте его с помощью этого помощника:

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

Применение:

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

Тестирование:

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

Вывод

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

Вы получите сложность O(n*n) .


Более оптимизированный способ – использовать таблицы Lookup:

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

Что дает вам O(2*n)O(n)

В результате у вас будет следующая структура (показана LinqPad):

введите описание изображения здесь

Вы можете использовать запрос ниже базы данных, чтобы получить список категорий с родительскими и дочерними отношениями:

 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 

Надеюсь, это поможет вам.

используя алгоритм Илья Иванов ( см. выше ), я сделал метод более общим.

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

Применение :

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

Вот небольшой пример, который я взбивал. Это довольно «общий».

Можно также сделать общий подход, определив интерфейс (который затем позволит упростить аргументы функции), однако я решил не делать этого. В любом случае функции «mapper» и selector позволяют это работать в разных типах.

Также обратите внимание, что это не очень эффективная реализация (поскольку она поддерживает все возможные дочерние элементы для всех поддеревьев и многократно повторяет их), но может быть подходящей для данной задачи. В прошлом я также использовал подход Dictionary , который имеет лучшие границы, но мне не хотелось писать так:

Это выполняется как «программа LINQPad C #». Наслаждайтесь!

 // 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(); } 
  • Алгоритм линейного времени для 2-SUM
  • Как вычислить число 3D Morton (чередуйте биты 3 ints)
  • Как рассчитать угол из трех точек?
  • Преобразование равномерного распределения в нормальное распределение
  • Определите, перекрываются ли два прямоугольника друг с другом?
  • Как найти элемент массива, который повторяется как минимум N / 2 раза?
  • Ширина первой Vs Глубина
  • Каковы различия между деревьями сегментов, деревьями интервалов, двоичными индексированными деревьями и деревьями диапазона?
  • Как заменить все вхождения символа в строке?
  • Big O при добавлении разных подпрограмм
  • std :: map, как сортировать по значению, затем по ключу
  • Давайте будем гением компьютера.