1

我有一个List<Element>对象集合 ( )，如下所述：

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

我基于读入的一些 XML 构建了一个对象List<Element>集合Element，对此我非常满意。目前如何实现对这些元素的搜索让我不解，但想知道是否有更好的解决方案。

集合的结构如下所示：

- 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）是否合理？

4

3 回答 3

1

Recursion is one way of implementing a tree search where you visit elements in depth-first order. You can implement the same algorithm with a loop instead of recursion by using a stack data structure to store the nodes of your tree that you need to visit.

If you use the same algorithm with a queue instead of a stack, the search would proceed in breath-first order.

In both cases the general algorithm looks like this:

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

Note that the algorithm is not recursive: it uses an explicit collection of nodes to save the current state of the search, whereas a recursive implementation uses the call stack for the same purpose. If nodes is a Stack<Element>, the search proceeds in depth-first order; if nodes is a Queue<Element>, the search proceeds in breadth-first order.

于 2013-07-13T13:25:39.337 回答
0

You can re-use existing components designed specifically for traversing in different ways, such as NETFx IEnumerable.Traverse Extension Method. It allows you to depth or breadth first. It lets you traverse an enumerable tree, depth or breadth first.

Example to get a flattened enumerable of directories:

IEnumerable<DirectoryInfo> directories = ... ;

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

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

For BreadhFirst it uses Queue<T> internally and for DepthFirst it uses Stack<T> internally.

It is not traversing nodes parallell and unless the traversal is resource demanding it isn't appropriate to use parallellism at this level. But that depends on the context.

于 2013-07-13T13:25:26.987 回答
0

我从某处抓到了这一点，它不是我的，但我无法提供指向它的链接。这个类为递归搜索展平了一个树视图，看起来它应该为你做同样的事情。

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

我找到了我从中获得的链接 - 它非常易于使用。看一看。是否有在 TreeView.Nodes 集合中搜索 TreeNode.Text 字段的方法？

于 2013-07-13T13:33:08.090 回答