gpt4 book ai didi

algorithm - 递归地执行广度优先搜索

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:11:23 26 4
gpt4 key购买 nike

假设您想要递归地实现二叉树的广度优先搜索。你会怎么做?

是否可以仅使用调用堆栈作为辅助存储?

最佳答案

(我假设这只是某种思维练习,甚至是一个技巧性的家庭作业/面试问题,但我想我可以想象一些奇怪的场景,由于某种原因你不允许任何堆空间[一些真的很糟糕的自定义内存管理器?一些奇怪的运行时/操作系统问题?]而你仍然可以访问堆栈......)

广度优先遍历传统上使用队列,而不是堆栈。队列和堆栈的性质非常相反,因此尝试使用调用堆栈(这是一个堆栈,因此得名)作为辅助存储(队列)几乎注定要失败,除非你正在做调用堆栈有些愚蠢可笑,你不应该这样。

出于同样的原因,您尝试实现的任何非尾递归本质上都是在算法中添加堆栈。这使得它不再对二叉树进行广度优先搜索,因此传统 BFS 的运行时等不再完全适用。当然,您总是可以轻松地将任何循环转换为递归调用,但这不是任何有意义的递归。

但是,正如其他人所展示的那样,有一些方法可以以一定的代价实现遵循 BFS 语义的东西。如果比较的代价是昂贵的但节点遍历是便宜的,那么作为@Simon Buchan确实如此,您可以简单地运行迭代深度优先搜索,只处理叶子。这意味着堆中没有存储增长的队列,只有一个局部深度变量,并且随着树一次又一次地遍历,堆栈在调用堆栈上一次又一次地建立起来。而作为 @Patrick注意,无论如何,由数组支持的二叉树通常以广度优先遍历顺序存储,因此对其进行广度优先搜索是微不足道的,也不需要辅助队列。

关于algorithm - 递归地执行广度优先搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2549541/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com