c# - 我如何有效地搜索这个层次结构？

Question

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

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

我想编写一个方法，在给定指定的代码 的情况下返回一个特定的节点。通常我只会通过层次结构进行递归遍历以找到节点，但我担心性能。层级中会有几千个节点，这个方法会被调用很多很多次。

我如何构建它以使其更快？我是否可以使用现有的数据结构，该结构可能在 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)
}  

如果你知道根，用法将是:

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

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