通过递归检查父子关系C＃来构建树类型列表
我有一个具有自身列表的类，因此它可以在树结构中表示。
我正在拉这些类的平面列表，并希望解决它。
public class Group { public int ID {get;set;} public int? ParentID {get;set;} public List Children {get;set;} } 我希望能够做到以下几点
List flatList = GetFlatList() //I CAN ALREADY DO THIS List tree = BuildTree(flatList);
如果不明显，则ParentID与其父组的ID属性相关。
编辑
关于为什么我返回列表而不是单个对象存在一些混淆。
我正在构建一个包含项目列表的UI元素，每个元素都有一个孩子。 所以初始列表没有根节点。 到目前为止，似乎所有的解决方案都不起作用。
这意味着我基本上需要使用Group类的树类型结构列表。
我不知道为什么你希望你的BuildTree方法返回List – 树需要有根节点，所以你应该期望它返回单个Group元素，而不是列表。
我会在IEnumerable上创建一个扩展方法：
public static class GroupEnumerable { public static IList BuildTree(this IEnumerable 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> 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 (); } } }
用法
var flatList = new List() { 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();
以下是如何在一行中执行此操作：
static void BuildTree(List items) { items.ForEach(i => i.Children = items.Where(ch => ch.ParentID == i.ID).ToList()); }
你可以像这样调用它：
BuildTree(flatList);
如果最后你想获得父级为null的节点（即顶级节点），你可以简单地这样做：
static List BuildTree(List items) { items.ForEach(i => i.Children = items.Where(ch => ch.ParentID == i.ID).ToList()); return items.Where(i => i.ParentID == null).ToList(); }
如果你想让它成为一个扩展方法，你可以在方法签名中添加this ：
static List BuildTree(this List items)
然后你可以像这样调用它：
var roots = flatList.BuildTree();
我尝试了建议的解决方案，并发现它们给我们提供了O（n ^ 2）复杂度。
在我的情况下（我有大约50k项目将被构建到树中）这是完全不可接受的。
我得出以下解决方案（假设每个项目只有一个父项，所有父项都存在于列表中），复杂度为O（n * log（n））[n次getById，getById具有O（log（n））复杂度] ：
static List- BuildTreeAndReturnRootNodes(List
- 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 Program { static void Main(string[] args) { var flatItems = new List- () { 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
- BuildTreeAndReturnRootNodes(List
- 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
- Children = new List
- (); } }