我有一个对象集合(List<Element>
),如下所述:
class Element
{
string Name;
string Value;
ICollection<Element> ChildCollection;
IDictionary<string, string> Attributes;
}
我基于在其中读取的一些XML构建了Element
对象的List<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)
目前,我正在使用递归来搜索每个顶级(A、B、C)Element
的Attributes
字典中的特定KeyValuePair
。如果我在顶级Element
中找不到它,我会以相同的方式开始搜索它的ChildElement
集合(1、1.1、2、2.1、n等)。
我想知道的是,是否有更好的方法来实现对这些对象的搜索,或者在这种情况下递归是否是更好的答案,我是否应该像现在这样实现搜索,top->child->child->等等,或者我是否应该以其他方式搜索,比如先搜索所有顶级?
我可以,使用TPL并行搜索每个顶层(A、B、C)是否合理?
递归是实现树搜索的一种方法,您可以在树搜索中按深度优先顺序访问元素。通过使用堆栈数据结构来存储需要访问的树的节点,可以使用循环而不是递归来实现相同的算法。
如果对队列而不是堆栈使用相同的算法,则搜索将按呼吸优先顺序进行。
在这两种情况下,通用算法如下所示:
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>
,则搜索按广度优先顺序进行。
我从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)));
}
}
我找到了这个链接,它很容易使用。看一看是否有在TreeView.Nodes集合中搜索TreeNode.Text字段的方法?
您可以重用专门为以不同方式遍历而设计的现有组件,例如NETFx IEnumerable.Traverse扩展方法。它允许你先深入或广度。它允许您遍历可枚举树,深度或广度优先。
获取扁平可枚举目录的示例:
IEnumerable<DirectoryInfo> directories = ... ;
IEnumerable<DirectoryInfo> allDirsFlattened = directories.Traverse(TraverseKind.BreadthFirst, dir => dir.EnumerateDirectories());
foreach (DirectoryInfo directoryInfo in allDirsFlattened)
{
...
}
对于BreadhFirst,它使用Queue<T>内部,对于DepthFirst,它使用Stack<T>内部。
它不是并行遍历节点,除非遍历需要资源,否则在这个级别上使用并行性是不合适的。但这取决于具体情况。