将项目列表转换为树的好的通用方法

我有类别列表：

╔════╦═════════════╦═════════════╗ ║ 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; } 

进入这一个：

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

普遍的方式？ //通用不仅意味着提到的课程。

你有一些聪明的想法吗？ ;）

---

数据：

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

Answer 1

如果你想要通用方法，你需要一个额外的类：

 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 

Answer 2

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

这是我掀起的一个小例子。 它非常“通用”。

也可以通过定义接口（然后允许简化函数参数）来制定通用方法 – 但是，我选择不这样做。 在任何情况下，“映射器”和选择器function允许它跨不同类型工作。

还要注意，这不是一个非常有效的实现（因为它保留所有子树的所有可能的子节点并重复迭代这样），但可能适合于给定的任务。 在过去我也使用了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(); } 

Answer 5

使用Ilya Ivanov算法（ 见上文 ），我使该方法更通用。

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