如何有效地搜索此层次结构？

Question

我有一个如下所示的数据结构:

public class Node
{
     public string Code { get; set; }
     public string Description { get; set; }
     ...
     public List<Node> Children { get; set; }
}

我想编写一个方法,在给定指定的情况下返回特定节点Code.通常我会在层次结构中进行递归遍历以找到节点,但我关注性能.层次结构中将有数千个节点,并且此方法将被多次调用.

如何构建它以使其更快？我是否可以使用可能Code在保留层次结构的同时执行二进制搜索的现有数据结构,而无需自己重新实现某种形式的二进制搜索？

Answer 1

将所有节点添加到字典中,并将代码作为键.(你可以做一次),字典中的查找基本上是O(1).

void FillDictionary(Dictionary<string, Node> dictionary, Node node)
{
  if (dictionary.ContainsKey(node.Code))
    return;

  dictionary.Add(node.Code, node);

  foreach (Node child in node.Children)
    FillDictionary(dictionary, child)
}  

如果你知道root,用法将是:

var dictionary = new Dictionary<string, Node>();
FillDictionary(dictionary, rootNode);

如果不这样做,您可以FillDictionary()使用相同的字典在所有节点上调用该方法.