通过递归检查父子关系构建树类型列表 C#
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15867478/
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
Build tree type list by recursively checking parent-child relationship C#
提问by TheJediCowboy
I have One class that has a list of itself so it can be represented in a tree structure.
我有一个类，它有自己的列表，因此可以用树结构表示。
I am pulling a flat list of these classes and want to unflatten it.
我正在拉这些类的平面列表，并希望将其解压。
public class Group
{
public int ID {get;set;}
public int? ParentID {get;set;}
public List<Group> Children {get;set;}
}
I want to be able to do the following
我希望能够做到以下几点
List<Group> flatList = GetFlatList() //I CAN ALREADY DO THIS
List<Group> tree = BuildTree(flatList);
The ParentID related to the ID property on its parent group if that wasnt obvious.
如果不明显，则 ParentID 与其父组上的 ID 属性相关。
EDIT
编辑
There is some confusion as to why I am returning a list and not a single object.
关于为什么我返回列表而不是单个对象存在一些困惑。
I am building a UI element that has a list of items, each of why has a child. So the initial list DOES NOT have a root node. It seems all of the solutions so far do not work.
我正在构建一个 UI 元素，其中包含一个项目列表，每个项目都有一个子项。所以初始列表没有根节点。似乎到目前为止所有的解决方案都不起作用。
What this means is I essentially need a list of tree type structures using Group class.
这意味着我本质上需要一个使用 Group 类的树型结构列表。
采纳答案by MarcinJuraszek
I have no idea why you want your BuildTreemethod return List<Group>- tree needs to have root node, so you should expect it to return single Groupelement, not a list.
我不知道你为什么想要你的BuildTree方法返回List<Group>- 树需要有根节点，所以你应该期望它返回单个Group元素，而不是一个列表。
I would create an extension method on IEnumerable<Group>:
我会创建一个扩展方法IEnumerable<Group>：
public static class GroupEnumerable
{
public static IList<Group> BuildTree(this IEnumerable<Group> source)
{
var groups = source.GroupBy(i => i.ParentID);
var roots = groups.FirstOrDefault(g => g.Key.HasValue == false).ToList();
if (roots.Count > 0)
{
var dict = groups.Where(g => g.Key.HasValue).ToDictionary(g => g.Key.Value, g => g.ToList());
for (int i = 0; i < roots.Count; i++)
AddChildren(roots[i], dict);
}
return roots;
}
private static void AddChildren(Group node, IDictionary<int, List<Group>> source)
{
if (source.ContainsKey(node.ID))
{
node.Children = source[node.ID];
for (int i = 0; i < node.Children.Count; i++)
AddChildren(node.Children[i], source);
}
else
{
node.Children = new List<Group>();
}
}
}
Usage
用法
var flatList = new List<Group>() {
new Group() { ID = 1, ParentID = null }, // root node
new Group() { ID = 2, ParentID = 1 },
new Group() { ID = 3, ParentID = 1 },
new Group() { ID = 4, ParentID = 3 },
new Group() { ID = 5, ParentID = 4 },
new Group() { ID = 6, ParentID = 4 }
};
var tree = flatList.BuildTree();
回答by JLRishe
Here's how you can do this in one line:
以下是如何在一行中执行此操作：
static void BuildTree(List<Group> items)
{
items.ForEach(i => i.Children = items.Where(ch => ch.ParentID == i.ID).ToList());
}
You can just call it like this:
你可以这样称呼它：
BuildTree(flatList);
If at the end you want to get the nodes whose parent is null (i.e. the top-level nodes), you can simply do this:
如果最后你想获得父节点为空的节点（即顶级节点），你可以简单地这样做：
static List<Group> BuildTree(List<Group> items)
{
items.ForEach(i => i.Children = items.Where(ch => ch.ParentID == i.ID).ToList());
return items.Where(i => i.ParentID == null).ToList();
}
And if you want to make it an extension method, you can just add thisin the method signature:
如果你想让它成为一个扩展方法，你可以this在方法签名中添加：
static List<Group> BuildTree(this List<Group> items)
Then you can call it like this:
然后你可以这样称呼它：
var roots = flatList.BuildTree();
回答by Dmitry Andrievsky
I tried solutions suggested and figured out that they give us about O(n^2) complexity.
我尝试了建议的解决方案，并发现它们为我们提供了 O(n^2) 复杂度。
In my case (I have about 50k items to be built into tree) it was completely unacceptable.
就我而言（我有大约 5 万个项目要构建到树中），这是完全不可接受的。
I came to the following solution (assuming that each item has only one parent and all parents exist in the list) with complexity O(n*log(n)) [n times getById, getById has O(log(n)) complexity]:
我来到了以下解决方案（假设每个项目只有一个父项并且列表中存在所有父项），复杂度为 O(n*log(n)) [n 次 getById，getById 的复杂度为 O(log(n))] ：
static List<Item> BuildTreeAndReturnRootNodes(List<Item> flatItems)
{
var byIdLookup = flatItems.ToLookup(i => i.Id);
foreach (var item in flatItems)
{
if (item.ParentId != null)
{
var parent = byIdLookup[item.ParentId.Value].First();
parent.Children.Add(item);
}
}
return flatItems.Where(i => i.ParentId == null).ToList();
}
Full code snippet:
完整代码片段：
class Program
{
static void Main(string[] args)
{
var flatItems = new List<Item>()
{
new Item(1),
new Item(2),
new Item(3, 1),
new Item(4, 2),
new Item(5, 4),
new Item(6, 3),
new Item(7, 5),
new Item(8, 2),
new Item(9, 3),
new Item(10, 9),
};
var treeNodes = BuildTreeAndReturnRootNodes(flatItems);
foreach (var n in treeNodes)
{
Console.WriteLine(n.Id + " number of children: " + n.Children.Count);
}
}
// Here is the method
static List<Item> BuildTreeAndReturnRootNodes(List<Item> flatItems)
{
var byIdLookup = flatItems.ToLookup(i => i.Id);
foreach (var item in flatItems)
{
if (item.ParentId != null)
{
var parent = byIdLookup[item.ParentId.Value].First();
parent.Children.Add(item);
}
}
return flatItems.Where(i => i.ParentId == null).ToList();
}
class Item
{
public readonly int Id;
public readonly int? ParentId;
public Item(int id, int? parent = null)
{
Id = id;
ParentId = parent;
}
public readonly List<Item> Children = new List<Item>();
}
}
