recherche de collection récursive

Question

J'ai une collection (List<Element>) d'objets tel que décrit ci-dessous:

class Element 
{ 
    string Name; 
    string Value; 
    ICollection<Element> ChildCollection; 
    IDictionary<string, string> Attributes; 
} 

Je construis une base sur certains XML que je lis dans la collection List<Element> de Element objets, ce que je suis tout à fait satisfait. Comment mettre en œuvre la recherche de ces éléments me a actuellement, non perplexe, mais je me demande s'il existe une meilleure solution.

La structure de la collection ressemble à quelque chose comme ceci:

- Element (A) 
    - Element (A1) 
    - Element (A1.1) 
    - Element (A2) 
- Element (B) 
    - Element (B1) 
    - Element (B1.1) 
    - Element (B1.2) 
- Element (C) 
    - Element (C1) 
    - Element (C2) 
    - Element (C3) 

Actuellement, je suis en utilisant récursion pour rechercher le dictionnaire Attributes de chaque niveau (A, B, C) Element pour un KeyValuePair particulier. Si je ne le trouve pas dans le niveau supérieur Element je commence à chercher sa collection ChildElement (1, 1.1, 2, 2.1, n, etc.) de la même manière. Ce qui m'intéresse est de savoir s'il existe une meilleure méthode pour implémenter une recherche sur ces objets ou si la récursivité est la meilleure réponse dans ce cas, si je devais implémenter la recherche comme je suis actuellement, top -> child - > enfant -> etc. ou si je devrais chercher d'une autre manière comme tous les premiers niveaux en premier?

Pourrais-je, et serait-il raisonnable d'utiliser le TPL pour rechercher chaque niveau supérieur (A, B, C) en parallèle?

Answer 1

La récursion est une façon d'implémenter une recherche arborescente dans laquelle vous visitez des éléments en profondeur. Vous pouvez implémenter le même algorithme avec une boucle au lieu de la récursion en utilisant une structure de données de pile pour stocker les noeuds de votre arbre que vous devez visiter.

Si vous utilisez le même algorithme avec une file d'attente au lieu d'une pile, la recherche se déroule dans l'ordre de la première respiration.

Dans les deux cas, l'algorithme général ressemble à ceci:

var nodes = ... // some collection of nodes 
nodes.Add(root); 
while (nodes.Count != 0) { 
    var current = nodes.Remove ... // Take the current node from the collection. 
    foreach (var child in current.ChildCollection) { 
     nodes.Add(child); 
    } 
    // Process the current node 
    if (current.Attributes ...) { 
     ... 
    } 
} 

Notez que l'algorithme n'est pas récursive: il utilise une collection explicite de nodes pour sauver l'état actuel de la recherche, alors qu'une utilisation de mise en œuvre récursives la pile d'appels dans le même but. Si nodes est Stack<Element>, la recherche se poursuit par depth-first order; si nodes est Queue<Element>, la recherche se poursuit en breadth-first order.

Answer 2

Vous pouvez réutiliser des composants existants conçus spécifiquement pour le déplacement de différentes manières, tels que NETFx IEnumerable.Traverse Extension Method. Il vous permet d'abord de la profondeur ou de la largeur. Il vous permet de traverser un arbre énumérable, profondeur ou largeur en premier.

Exemple pour obtenir un dénombrable aplaties des répertoires:

IEnumerable<DirectoryInfo> directories = ... ; 

IEnumerable<DirectoryInfo> allDirsFlattened = directories.Traverse(TraverseKind.BreadthFirst, dir => dir.EnumerateDirectories()); 

foreach (DirectoryInfo directoryInfo in allDirsFlattened) 
{ 
    ... 
} 

Pour BreadhFirst il utilise Queue<T> en interne et pour DepthFirst utilise Stack<T> en interne.

Il ne traverse pas les nœuds parallèlement et à moins que la traversée ne soit exigeante en ressources, il n'est pas approprié d'utiliser le parallélisme à ce niveau. Mais cela dépend du contexte.

Answer 3

J'ai attrapé ce peu de SO quelque part, ce n'est pas le mien mais je ne peux pas fournir un lien vers lui.Cette classe aplatit une vue arborescente pour une recherche récursive, on dirait qu'elle devrait faire la même chose pour vous.

public static class SOExtension 
{ 
    public static IEnumerable<TreeNode> FlattenTree(this TreeView tv) 
    { 
     return FlattenTree(tv.Nodes); 
    } 

    public static IEnumerable<TreeNode> FlattenTree(this TreeNodeCollection coll) 
    { 
     return coll.Cast<TreeNode>() 
        .Concat(coll.Cast<TreeNode>() 
           .SelectMany(x => FlattenTree(x.Nodes))); 
    } 
} 

J'ai trouvé le lien que j'ai obtenu à partir de - c'est très facile à utiliser. regarde. Is there a method for searching for TreeNode.Text field in TreeView.Nodes collection?