执行广度优先搜索递归 [英] Performing Breadth First Search recursively

问题描述

比方说，你想实现一个广度优先搜索二叉树的的递归的。你会如何​​做呢？

Let's say you wanted to implement a breadth-first search of a binary tree recursively. How would you go about it?

仅使用调用堆栈作为辅助存储，可以吗？

Is it possible using only the call-stack as auxiliary storage?

推荐答案

（我假定这只是某种思想运动，甚至一招功课/面试问题，但我想我能想象一些奇怪的场景在这里你不允许任何堆空间出于某种原因[一些非常糟糕的自定义的内存管理器？一些奇怪的运行/ OS的问题？]，而你仍然可以访问堆栈...）

(I'm assuming that this is just some kind of thought exercise, or even a trick homework/interview question, but I suppose I could imagine some bizarre scenario where you're not allowed any heap space for some reason [some really bad custom memory manager? some bizarre runtime/OS issues?] while you still have access to the stack...)

广度优先遍历传统上采用了队列，而不是一个堆栈。队列的性质和一叠是pretty的多相反，所以欲以调用堆栈（这是一个堆栈，因此而得名）作为辅助存储（队列）被pretty的多注定要失败的，除非你正在做一些愚蠢可笑的调用堆栈，你不应该。

Breadth-first traversal traditionally uses a queue, not a stack. The nature of a queue and a stack are pretty much opposite, so trying to use the call stack (which is a stack, hence the name) as the auxiliary storage (a queue) is pretty much doomed to failure, unless you're doing something stupidly ridiculous with the call stack that you shouldn't be.

在同样的道理，任何一个非尾递归试图实现实质上增加了栈算法的性质。这使得它不再广度上的二叉树第一搜索，并且因此运行时和诸如此类的传统的BFS不再完全适用。当然，你可以随时把平凡任何环路成一个递归调用，但这不是任何形式的有意义的递归。

On the same token, the nature of any non-tail recursion you try to implement is essentially adding a stack to the algorithm. This makes it no longer breadth first search on a binary tree, and thus the run-time and whatnot for traditional BFS no longer completely apply. Of course, you can always trivially turn any loop into a recursive call, but that's not any sort of meaningful recursion.

然而，也有办法，就证明了别人，来实现一些如下BFS的语义付出一定的代价。如果比较的成本是昂贵的，但节点遍历是廉价，那么作为<一个href="http://stackoverflow.com/questions/2549541/performing-breadth-first-search-recursively/2549825#2549825">@Simon巴肯做，你可以简单地运行一个反复的深度优先搜索，只处理了叶子。这意味着没有增长的队列存储在堆中，只是一个局部深度变量，堆栈被建立起来，并在调用堆栈作为树遍历一遍又一遍。而作为<一个href="http://stackoverflow.com/questions/2549541/performing-breadth-first-search-recursively/2549744#2549744">@Patrick注意到，二叉树的数组，通常存储在广度优先遍历顺序，无论如何，所以在一个广度优先搜索将是微不足道的，也无需辅助的队列。

However, there are ways, as demonstrated by others, to implement something that follows the semantics of BFS at some cost. If the cost of comparison is expensive but node traversal is cheap, then as @Simon Buchan did, you can simply run an iterative depth-first search, only processing the leaves. This would mean no growing queue stored in the heap, just a local depth variable, and stacks being built up over and over on the call stack as the tree is traversed over and over again. And as @Patrick noted, a binary tree backed by an array is typically stored in breadth-first traversal order anyway, so a breadth-first search on that would be trivial, also without needing an auxiliary queue.

这篇关于执行广度优先搜索递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！