遍历一般的树结构在C＃中的任意节点开始

我需要在这两个深度优先和广度优先遍历顺序任意树树的遍历算法。棘手的部分是我需要能够从任意节点开始并继续直到另一个特定节点被遍历。现在遍历一般的树结构在C＃中的任意节点开始

，我可以使用任何普通的算法，而忽略了经过的各个节点，直到我打的起始节点，并一直持续到年底节点（我目前做的），但是这是丑陋和低效。

请提出任何建议。

UPDATE：我的每一个节点有与之相关的ID。在某些情况下，我有开始和结束节点引用。在其他情况下，我给了两个ID，我通过检查它们的ID来检查给定节点是开始节点还是结束节点。我使用深度优先遍历来查找开始节点。开始和结束节点都可以位于层次结构中的任何位置。我希望有人能够提出一个想法，我已经给出了对起始节点和终止节点的引用。顺便说一句，在该树中的节点按照排序顺序，从0对于每个节点的子节点的开始和有一个根节点

来源

2011-10-17 Kemal Erdogan

如何找到树中的开始节点而不遍历它？ – BrokenGlass

你已经有*节点了吗？否则，您需要第二个数据结构来加速查找开始/结束节点。 – harold

请指定你的树的结构。有没有排序顺序？节点如何相关？ –

我觉得你在做什么是应该做的最有效的方式。特别是如果你正在使用任意树。

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

我不明白，你可以做任何优化。

来源

2011-10-17 16:41:10 DarthVader

不是

Traverse(RootNode, StartNode, EndNode)

通行证实际上排序作为根的起始节点

Traverse(StartNode, EndNode)

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

来源

2011-10-17 16:26:05

如果你将不得不回答很多不相关的查询，并且你需要提供一个路径（而不是仅仅说存在或不存在），那么你不能比现在的AFAIK做得更好。另一方面，如果您期望涉及少量特定节点的许多查询（例如，从A到B，C，D，E，F和G的路径是什么），那么您可以先计算来自该节点的minimum spanning tree，并使您的BFS更高效。

来源

2011-10-18 13:02:23 Jon

遍历一般的树结构在C＃中的任意节点开始

回答

相关问题