Рекурсивный поиск коллекции

Question

У меня есть коллекция (List<Element>) объектов, как описано ниже:

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

Я строю List<Element> коллекцию Element объектов на основе некоторого XML, что я читал в это я вполне доволен. Как реализовать поиск этих элементов в настоящее время имеет меня, а не тупик, но интересно, есть ли лучшее решение.

Структура коллекции выглядит примерно так:

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

В настоящее время я использую рекурсии для поиска Attributes словаря каждого верхнего уровня (A, B, C) Element для конкретного KeyValuePair. Если я не нахожу его на верхнем уровне Element, я начинаю искать его коллекцию ChildElement (1, 1.1, 2, 2.1, n и т. Д.) Таким же образом.

Что мне интересно, если есть лучший способ реализации поиска по этим объектам, или если рекурсия является лучшим ответом в этом случае, если я должен реализовать поиск, как я есть сейчас, top -> child - > child -> и т. д., или если я сначала должен искать другим способом, например, все верхние уровни?

Мог ли я, и было бы разумно использовать TPL для поиска по каждому верхнему уровню (A, B, C) параллельно?

Answer 1

Рекурсия - один из способов реализации поиска дерева, в котором вы посещаете элементы в глубине-первом порядке. Вы можете реализовать тот же алгоритм с циклом вместо рекурсии, используя структуру данных стека для хранения узлов вашего дерева, которые вам нужно посетить.

Если вы используете тот же алгоритм с очередью вместо стека, поиск будет действовать в первом порядке.

В обоих случаях общий алгоритм выглядит следующим образом:

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 ...) { 
     ... 
    } 
} 

Обратите внимание, что алгоритм не является рекурсивным: он использует явную коллекцию nodes, чтобы сохранить текущее состояние поиска, в то время как рекурсивный используется реализация стек вызовов для той же цели. Если nodes является Stack<Element>, поиск осуществляется в depth-first order; если nodes является Queue<Element>, поиск осуществляется в breadth-first order.

Answer 2

Вы можете повторно использовать существующие компоненты, предназначенные специально для перемещения по-разному, например NETFx IEnumerable.Traverse Extension Method. Это позволяет вам глубже или ширине. Он позволяет сначала пересекать перечислимое дерево, глубину или ширину.

Пример для получения сплюснутый перечислимых каталогов:

IEnumerable<DirectoryInfo> directories = ... ; 

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

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

Для BreadhFirst он использует Queue<T> внутренне и DepthFirst использует Stack<T> внутренне.

Он не пересекает узлы parallell, и если обход ресурса не требует использования параллелизма на этом уровне. Но это зависит от контекста.

Answer 3

Я схватил этот бит от SO где-то, его не мой, но я не могу предоставить ссылку на него.Этот класс Flattens out treeview для рекурсивного поиска, похоже, что он должен сделать то же самое для вас.

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

Я нашел ссылку, с которой я получил это - ее очень проста в использовании. Взгляни. Is there a method for searching for TreeNode.Text field in TreeView.Nodes collection?