C# 将项目列表转换为树的不错且通用的方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19648166/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Nice & universal way to convert List of items to Tree
提问by
I have list of categories:
我有类别列表：
╔════╦═════════════╦═════════════╗
║ 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 ║
╚════╩═════════════╩═════════════╝
Each category have a parent. When parent is 0 - that means it's the root category.
每个类别都有一个父级。当 parent 为 0 时 - 这意味着它是根类别。
What is the nicest wayto convert it to tree structure like below?
什么是最好的方式将其转换为树状结构下面？
In other words - how to bring data from this structure:
换句话说 - 如何从这个结构中获取数据：
class category
{
public int Id;
public int ParentId;
public string Name;
}
Into this one:
进入这个：
class category
{
public int Id;
public int ParentId;
public string Name;
public List<Category> Subcategories;
}
in universal way? // Universal means not only for mentioned class.
以普遍的方式？// 通用意味着不仅适用于提到的类。
Do you have some smart ideas? ;)
你有一些聪明的想法吗？;)
Data:
数据：
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),
};
采纳答案by Damian Drygiel
If you want to have universalmethod you''ll need an additional class:
如果你想拥有通用方法，你需要一个额外的类：
public class TreeItem<T>
{
public T Item { get; set; }
public IEnumerable<TreeItem<T>> Children { get; set; }
}
Then use it with this helper:
然后与这个助手一起使用它：
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))
};
}
}
}
Usage:
用法：
var root = categories.GenerateTree(c => c.Id, c => c.ParentId);
Testing:
测试：
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);
Output
输出
Sport
Balls
Shoes
Electronics
Cameras
Lenses
Tripod
Computers
Laptops
Empty
回答by Ilya Ivanov
foreach (var cat in categories)
{
cat.Subcategories = categories.Where(child => child.ParentId == cat.Id)
.ToList();
}
You'll get O(n*n)complexity.
你会得到O(n*n)复杂性。
More optimized way is to use Lookup tables:
更优化的方法是使用查找表：
var childsHash = categories.ToLookup(cat => cat.ParentId);
foreach (var cat in categories)
{
cat.Subcategories = childsHash[cat.Id].ToList();
}
Which gives you O(2*n)≈ O(n)
这给了你O(2*n)≈O(n)
As result, you'll have next structure (shown from LinqPad):
结果，您将拥有下一个结构（从 LinqPad 中显示）：
回答by Girish Vadhel
You can use below database query to get the list of categories with parent-child relations:
您可以使用以下数据库查询来获取具有父子关系的类别列表：
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
I hope this will help you out.
我希望这会帮助你。
回答by user2864740
Here is a little example I whipped up. It's pretty "Generic".
这是我提出的一个小例子。它非常“通用”。
One could also make a generic approach by defining an interface (which would then allow the function arguments to be simplified) - however, I chose not to do so. In any case, the "mapper" and selector functions allows this it work across distinct types.
还可以通过定义一个接口（然后允许简化函数参数）来制定通用方法 - 但是，我选择不这样做。在任何情况下，“映射器”和选择器函数都允许它跨不同类型工作。
Also note that this is nota very efficient implementation (as it keeps around all possible children for all subtrees and repeatedly iterates such), but may be suitable for the given task. In the past I have also used a Dictionary<key,collection>approach, which has better bounds, but I didn't feel like writing it that way :)
还要注意，这不是一个非常有效的实现（因为它保留了所有子树的所有可能的子树并重复迭代），但可能适用于给定的任务。过去我也使用过一种Dictionary<key,collection>方法，它有更好的界限，但我不想那样写:)
This runs as a "LINQPad C# Program". Enjoy!
这作为“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();
}
回答by Andrew
using Ilya Ivanovalgorithm (see above), i made the method more generic.
使用Ilya Ivanov算法（见上文），我使该方法更加通用。
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)]));
}
usage :
用法 ：
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
});
回答by Ярослав Виталиевич
Using Ilya Ivanovand Damian Drygielsolutions, I've written some code, that makes a tree with any collection and any levels of children, even if you exactly don't know, what nodes will be roots.
使用Ilya Ivanov和Damian Drygiel解决方案，我编写了一些代码，这些代码可以生成具有任何集合和任何级别子级的树，即使您完全不知道哪些节点将是根。
Tree node entry
树节点条目
public sealed class TreeNode<T, TKey>
{
public T Item { get; set; }
public TKey ParentId { get; set; }
public IEnumerable<TreeNode<T, TKey>> Children { get; set; }
}
Extension methods
扩展方法
public static class EnumerableExtensions
{
public static IEnumerable<TreeNode<T, TKey>> ToTree<T, TKey>(
this IList<T> collection,
Func<T, TKey> itemIdSelector,
Func<T, TKey> parentIdSelector)
{
var rootNodes = new List<TreeNode<T, TKey>>();
var collectionHash = collection.ToLookup(parentIdSelector);
//find root nodes
var parentIds = collection.Select(parentIdSelector);
var itemIds = collection.Select(itemIdSelector);
var rootIds = parentIds.Except(itemIds);
foreach (var rootId in rootIds)
{
rootNodes.AddRange(
GetTreeNodes(
itemIdSelector,
collectionHash,
rootId)
);
}
return rootNodes;
}
private static IEnumerable<TreeNode<T, TKey>> GetTreeNodes<T, TKey>(
Func<T, TKey> itemIdSelector,
ILookup<TKey, T> collectionHash,
TKey parentId)
{
return collectionHash[parentId].Select(collectionItem => new TreeNode<T, TKey>
{
ParentId = parentId,
Item = collectionItem,
Children = GetTreeNodes(
itemIdSelector,
collectionHash,
itemIdSelector(collectionItem))
});
}
}
Example:
例子：
//Test Item
public class TestTreeItem
{
public int Id { get; set; }
public int ParentId { get; set; }
public string Name { get; set; }
}
//Usage
var collection = new List<TestTreeItem>
{
new TestTreeItem {Id = 1, Name = "1", ParentId = 14},
new TestTreeItem {Id = 2, Name = "2", ParentId = 0},
new TestTreeItem {Id = 3, Name = "3", ParentId = 1},
new TestTreeItem {Id = 4, Name = "4", ParentId = 1},
new TestTreeItem {Id = 5, Name = "5", ParentId = 2},
new TestTreeItem {Id = 6, Name = "6", ParentId = 2},
new TestTreeItem {Id = 7, Name = "7", ParentId = 3},
new TestTreeItem {Id = 8, Name = "8", ParentId = 3},
new TestTreeItem {Id = 9, Name = "9", ParentId = 5},
new TestTreeItem {Id = 10, Name = "10", ParentId = 7}
};
var tree = collection.ToTree(item => item.Id, item => item.ParentId);
I hope, it helps someone. Enjoy
我希望，它可以帮助某人。享受
回答by Dmitry Pavlov
Yet another way with passing how to identify parent. Full code (including internal implementation of ITreeand xUnittest) is available as Gisthere: Nice & universal way to convert List of items to Tree
传递如何识别父母的另一种方式。完整代码（包括内部实现ITree和xUnit测试）可在Gist此处获得：Nice & Universal way to convert of items to Tree
Usage:
用法：
ITree<Category> tree = categories.ToTree((parent, child) => child.ParentId == parent.Id);
Proiduces:
产品：
<ROOT>
-Sports
--Balls
--Shoes
-Electronics
--Cameras
---Lenses
---Tripod
--Computers
---Laptops
-Empty
-Broken
Universal tree node interface:
通用树节点接口：
public interface ITree<T>
{
T Data { get; }
ITree<T> Parent { get; }
ICollection<ITree<T>> Children { get; }
bool IsRoot { get; }
bool IsLeaf { get; }
int Level { get; }
}
Extension method for collection:
采集扩展方法：
public static ITree<T> ToTree<T>(this IList<T> items, Func<T, T, bool> parentSelector)
{
if (items == null) throw new ArgumentNullException(nameof(items));
var lookup = items.ToLookup(
item => items.FirstOrDefault(parent => parentSelector(parent, item)),
child => child);
return Tree<T>.FromLookup(lookup);
}
