Langage C#
  1. Langage C#
  3. Construire la liste des types d’arborescence en vérifiant de manière récursive la relation parent-enfant C #
Intereting Posts
Enregistrement de fichiers sur Raspberry PI avec Windows IoT Comment sélectionner plusieurs contrôles en les faisant glisser avec la souris Comment faire un upsert avec MongoDB 2.0? SQLite avec VS2012 et .NET 4.5 – N’IMPORTE QUELLE génération de CPU Comment append un fournisseur d’appartenance ASP.NET dans un modèle de projet MVC 4 vide? Mise à jour des étiquettes asynchrones ASP.NET C # Copier les pixels du bitmap dans le canal alpha sur un autre bitmap Mettre à jour l’interface utilisateur à partir du fil de fond Conversion de tableau en IEnumerable Comment gérer les exceptions émises par les tâches dans Assert.Throws de xUnit .net? DocuSign RestApi – Erreur lors du téléchargement du document – TAB_REFERS_TO_MISSING_DOCUMENT Existe-t-il une extension Visual Studio 2010 pour sortinger les méthodes? Comment savoir si mon processus est exécuté en tant qu’administrateur? Entity Framework 4.1 – Entité de substitution (DBSet) avec filtre “L’expression doit être évaluée à un ensemble de nœuds.”

Construire la liste des types d’arborescence en vérifiant de manière récursive la relation parent-enfant C #

J’ai une classe qui a une liste d’elle-même afin qu’elle puisse être représentée dans une arborescence.

Je tire une liste à plat de ces classes et je veux la dégonfler. 

public class Group { public int ID {get;set;} public int? ParentID {get;set;} public List Children {get;set;} }

Je veux pouvoir faire ce qui suit 

 List flatList = GetFlatList() //I CAN ALREADY DO THIS List tree = BuildTree(flatList);

Le ParentID associé à la propriété ID de son groupe parent si ce n’était pas évident.

MODIFIER

Il y a une certaine confusion quant à la raison pour laquelle je retourne une liste et non un seul object.

Je construis un élément d’interface utilisateur qui a une liste d’éléments, chacun ayant pourquoi un enfant. Donc, la liste initiale N’A PAS de nœud racine. Il semble que toutes les solutions à ce jour ne fonctionnent pas.

Cela signifie que j’ai essentiellement besoin d’une liste de structures de type arborescente utilisant la classe Group.

Je ne sais pas pourquoi vous voulez que votre méthode BuildTree renvoie la List : l’arborescence doit avoir un nœud racine. Vous devez donc vous attendre à ce qu’elle renvoie un seul élément du Group , pas une liste.

Je créerais une méthode d’extension sur 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(); } } }

Usage 

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

Voici comment vous pouvez le faire en une seule ligne: 

 static void BuildTree(List items) { items.ForEach(i => i.Children = items.Where(ch => ch.ParentID == i.ID).ToList()); }

Vous pouvez simplement l’appeler comme ceci: 

 BuildTree(flatList);

Si à la fin vous voulez obtenir les noeuds dont le parent est nul (c’est-à-dire les noeuds de niveau supérieur), vous pouvez simplement faire ceci: 

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

Et si vous voulez en faire une méthode d’extension, vous pouvez simplement append this dans la signature de la méthode: 

 static List BuildTree(this List items)

Ensuite, vous pouvez l’appeler comme ceci: 

 var roots = flatList.BuildTree();

J’ai essayé les solutions suggérées et compris qu’elles nous donnaient une complexité de O (n ^ 2).

Dans mon cas (il me faut environ 50 000 éléments à intégrer dans l’arbre), c’était totalement inacceptable.

Je suis arrivé à la solution suivante (en supposant que chaque élément n’a qu’un seul parent et que tous les parents existent dans la liste) avec une complexité O (n * log (n)) [n fois getById, getById a une complexité 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(); }

Extrait de code complet: 

 class Program { static void Main(ssortingng[] 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(); } }