C#中的反向广度优先遍历
C#中的反向广度优先遍历
提问于 2010-04-05 22:40:31
谁有现成的C#反向广度优先遍历算法的实现？
通过反向广度优先遍历，我的意思是不是从公共节点开始搜索树，而是从底部开始搜索树，并逐渐收敛到公共节点。
让我们看看下图，这是广度优先遍历的输出：
在我的反向广度优先遍历中，9、10、11和12将是最先找到的几个节点(它们的顺序并不重要，因为它们都是第一顺序)。5、6、7和8是第二个找到的节点，依此类推。1将是找到的最后一个节点。
有什么想法或建议吗？
编辑:将“广度优先搜索”改为“广度优先遍历”，以澄清问题
回答 2
Stack Overflow用户
回答已采纳
发布于 2010-04-05 23:03:58
从rootNode运行一个普通的BFS并让depth[i] = linked list of nodes with depth i。因此，对于您的示例，您将拥有：
depth[1] = {1}, depth[2] = {2, 3, 4} etc.。你可以用一个简单的BFS搜索来构建它。然后打印depth[maxDepth]中的所有节点，然后打印depth[maxDepth - 1]中的节点等。
节点i的深度等于其父节点的深度+ 1。根节点的深度可以认为是1或0。
Stack Overflow用户
发布于 2010-04-05 22:54:27
使用堆栈和队列的组合。
使用队列执行“普通”BFS (我假设您已经知道要这样做)，并在遇到节点时继续在堆栈上推送节点。
一旦完成了BFS，堆栈将包含相反的BFS顺序。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2578932
复制相关文章
相似问题
腾讯云开发者
