最快树遍历

Question

我有一个相当大的树数据结构，将被更新(删除和添加节点，等等)。我必须使用广度优先方法遍历树，访问所有节点(一定宽度、深度(如7) )，并将其放到列表中。然后，函数将遍历节点，如果在列表中找到信息，则返回true。

这需要花费大量的时间来遍历节点。我不认为我应该用每个子节点映射每个节点，然后使用Dictionary提取节点并获取它的所有子节点(递归)。我该怎么做？最快的方法是映射彼此之间的所有节点，就像

Dictionary<Node, List<Node>>

• 节点，所有孩子的列表(包括孩子的孩子.)然后拉出节点，快速得到2,000个孩子。但是，如果一个节点在任何地方被添加或删除，那么所有的字典节点都需要被更新(这似乎是个麻烦)。另一种方法是在运行期间动态地循环它(这需要时间)。这是一个在树生成期间将所有东西映射到一起的问题，或者在运行时循环的问题。

处理这种情况的最佳方法是什么？任何想法，指示，评论，任何东西都是有帮助的。目前，此操作大约占用程序运行时间的25%。

Answer 1

如果您只是计算一个谓词，您可以在遍历树时直接这样做，您不需要首先将完整的树放入列表中--除非您缓存该列表。直接评估树节点上的谓词，您可以在第一次找到感兴趣的信息时就中断/停止遍历。