Construire la liste des types d'arbre en vérifiant récursivement la relation parent-enfant C#
j'ai une classe qui a une liste d'elle-même pour qu'elle puisse être représentée dans une structure arborescente.
je suis en train de tirer une liste plate de ces classes et je veux la découpler.
public class Group
{
public int ID {get;set;}
public int? ParentID {get;set;}
public List<Group> Children {get;set;}
}
je veux pouvoir faire ce qui suit
List<Group> flatList = GetFlatList() //I CAN ALREADY DO THIS
List<Group> tree = BuildTree(flatList);
la clause se rapportait à la propriété ID sur son groupe parent si cela n'était pas évident.
EDIT
il y a une certaine confusion quant à la raison pour laquelle je retourne une liste et pas une seule objet.
je construis un élément UI qui a une liste d'articles, chaque pourquoi a un enfant. Donc la liste initiale n'a pas de noeud racine. Il semble que toutes les solutions ne fonctionnent pas.
ce que cela signifie est que j'ai essentiellement besoin d'une liste de structures de type d'arbre en utilisant la classe de groupe.
3 réponses
je n'ai aucune idée de pourquoi vous voulez que votre BuildTree retour de méthode List<Group> - l'arbre doit avoir le noeud racine, donc vous devez vous attendre à ce qu'il retourne simple Group élément, et non une liste.
je créerais une méthode d'extension sur 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>();
}
}
}
Utilisation
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();
Voici comment vous pouvez le faire en une seule ligne:
static void BuildTree(List<Group> items)
{
items.ForEach(i => i.Children = items.Where(ch => ch.ParentID == i.ID).ToList());
}
Vous pouvez tout aussi bien l'appeler comme ceci:
BuildTree(flatList);
si à la fin vous voulez obtenir les noeuds dont le parent est nul (c.-à-d. les noeuds de haut niveau), vous pouvez simplement faire ceci:
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();
}
Et si vous voulez en faire une méthode d'extension, vous pouvez simplement ajouter this dans la méthode signature:
static List<Group> BuildTree(this List<Group> items)
Ensuite, vous pouvez l'appeler comme ceci:
var roots = flatList.BuildTree();
dans mon cas (j'ai environ 50k articles à construire dans l'arbre) c'était complètement inacceptable.
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();
}
Code complet 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>();
}
}