Поиск рекурсивной коллекции

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>поиск продолжается в порядке глубины; если nodes это Queue<Element>поиск продолжается в порядке по ширине.

Answer 2

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

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

Я нашел ссылку, по которой я это получил - ее очень легко использовать. посмотри. Есть ли метод для поиска поля TreeNode.Text в коллекции TreeView.Nodes?

Answer 3

Вы можете повторно использовать существующие компоненты, разработанные специально для обхода, различными способами, такими как 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>;; внутри.

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