6

我需要深度优先和广度优先遍历顺序的任意树的树遍历算法。棘手的部分是我需要能够从任意节点开始并继续直到遍历另一个特定节点。

现在,我可以使用任何普通算法并忽略遍历的节点,直到我到达开始节点并继续直到结束节点(我目前正在这样做),但这既丑陋又低效。

请有任何建议。

更新:我的每个节点都有一个与之关联的 id。在某些情况下,我有开始和结束节点引用作为开始。在其他情况下,我有两个 ID,我通过检查它们的 ID 来检查给定节点是开始节点还是结束节点。我使用深度优先遍历来查找起始节点。开始节点和结束节点都可以位于层次结构中的任何位置。我希望有人可以为我已经参考起始节点和结束节点的情况提出一个想法。BTW,树中的节点实际上是按照排序顺序排序的,一个节点的每个子节点从0开始,并且有一个根节点

4

3 回答 3

2

我认为你正在做的是最有效的方法。特别是如果您正在使用任意树。

给你一棵任意树,你需要找到开始遍历的节点。由于没有层次结构(即:它不是二叉树),您将不得不扫描节点(如果给定节点是叶节点或节点不在树中,您可能最终扫描超过一半的节点将不得不搜索整个树),直到找到要开始的节点。找到节点后,您可以启动 DF Traversal 或 BF Traversal。

我没有看到您可以做的任何优化。

于 2011-10-17T16:41:10.740 回答
0

而不是

Traverse(RootNode, StartNode, EndNode)

将起始节点作为根传递

Traverse(StartNode, EndNode)

但是,如果要返回不是起始节点子节点的节点,则必须继续使用当前方法。

于 2011-10-17T16:26:05.513 回答
0

如果您将不得不回答许多不相关的查询,并且您需要提供一条路径(而不是仅仅说存在与否),那么您无法比现在的 AFAIK 做得更好。

另一方面,如果您期望大量查询涉及少量特定节点(例如,从 A 到 B、C、D、E、F 和 G 的路径是什么?)那么您可以首先计算最小生成树从那个节点开始,让你的 BFS 更有效率。

于 2011-10-18T13:02:23.877 回答