Java或C++中的递归广度优先旅行函数？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2969033/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Recursive breadth-first travel function in Java or C++?
提问by joejax
Here is a java code for breadth-first travel:
这是广度优先旅行的java代码：
void breadthFirstNonRecursive(){
Queue<Node> queue = new java.util.LinkedList<Node>();
queue.offer(root);
while(!queue.isEmpty()){
Node node = queue.poll();
visit(node);
if (node.left != null)
queue.offer(node.left);
if (node.right != null)
queue.offer(node.right);
}
}
Is it possible to write a recursive function to do the same?
是否可以编写一个递归函数来做同样的事情？
At first, I thought this would be easy, so I came out with this:
起初，我认为这很容易，所以我想出了这个：
void breadthFirstRecursive(){
Queue<Node> q = new LinkedList<Node>();
breadthFirst(root, q);
}
void breadthFirst(Node node, Queue<Node> q){
if (node == null) return;
q.offer(node);
Node n = q.poll();
visit(n);
if (n.left != null)
breadthFirst(n.left, q);
if (n.right != null)
breadthFirst(n.right, q);
}
Then I found it doesn't work. It is actually does the same thing as this:
然后我发现它不起作用。它实际上与此相同：
void preOrder(Node node) {
if (node == null) return;
visit(node);
preOrder(node.left);
preOrder(node.right);
}
Has any one thought about this before?
有没有人想过这个问题？
采纳答案by Stephen
I can't imagine whyyou'd want to, when you have a perfectly good iterative solution, but here you go ;)
我无法想象你为什么想要，当你有一个非常好的迭代解决方案时，但你去;)
void breadth_first(Node root):
Queue q;
q.push(root);
breadth_first_recursive(q)
void breadth_first_recursive(Queue q):
if q.empty() return;
Node n = q.pop()
print "Node: ", n
if (n.left) q.push(n.left)
if (n.right) q.push(n.right)
breadth_first_recursive(q)
I should add that if you really want to traverse the nodes of the tree recursively, then you could do a DFS with a levelparameter, and output nodes only at level, then recurse up. But that's just crazy talk, because you'd revisit nodes wayyyyy too many times... Just accept that BFS is an iterative algorithm. :)
我应该补充一点，如果您真的想递归遍历树的节点，那么您可以使用level参数执行 DFS ，并且仅在 处输出节点level，然后向上递归。但这只是胡说八道，因为你会多次重访节点……接受 BFS 是一种迭代算法。:)
回答by ob1
The BFS algorithm is not a recursive algorithm (as opposed to DFS).
BFS 算法不是递归算法（与 DFS 相对）。
One couldtry writing a recursive function that emulates the algorithm but that would end up quite bizzare. What would be the point in doing this ?
一个可以尝试写一个模拟算法递归函数但最终会相当的bizzare。这样做有什么意义？
回答by gustafc
You can use iterative deepening depth-first search, which effectively is a breadth-first algorithm that uses recursion. It's even better than BFS if you have a high branching factor, as it doesn't use much memory.
您可以使用迭代深化深度优先搜索，它实际上是一种使用递归的广度优先算法。如果你有一个高分支因子，它甚至比 BFS 更好，因为它不使用太多内存。
回答by jim
This is not going to be satisfying to everyone -- I am sure. With all respect to everyone. To the people who ask what is the point? The point is that we believe that every iterative algorithm has also a (easy?) recursive solution. Here is a solution by "sisis" from stackoverflow.
这不会让每个人都满意——我敢肯定。尊重每一个人。那些问有什么意义的人？关键是我们相信每个迭代算法也有一个（简单的？）递归解决方案。这是来自stackoverflow的“sisis”的解决方案。
BFS(Q)
{
if (|Q| > 0)
v < - Dequeue(Q)
Traverse(v)
foreach w in children(v)
Enqueue(Q, w)
BFS(Q)
}
It has certain amount of funninest in it, but it not clear that it violates any recursive rules. If it does not violate any recursive rules, then it should be accepted. IMHO.
它有一定数量的最有趣，但不清楚它是否违反了任何递归规则。如果它不违反任何递归规则，那么它应该被接受。恕我直言。
回答by ThePatelGuy
A Simple BFS and DFS recursion: Just push/offer the root node of tree in stack/queue and call these functions!
一个简单的 BFS 和 DFS 递归：只需在堆栈/队列中推送/提供树的根节点并调用这些函数！
public void breadthFirstSearch(Queue queue) {
if (queue.isEmpty())
return;
Node node = (Node) queue.poll();
System.out.println(node + " ");
if (node.right != null)
queue.offer(node.right);
if (node.left != null)
queue.offer(node.left);
breadthFirstSearch(queue);
}
}
public void depthFirstSearch(Stack stack) {
if (stack.isEmpty())
return;
Node node = (Node) stack.pop();
System.out.println(node + " ");
if (node.right != null)
stack.push(node.right);
if (node.left != null)
stack.push(node.left);
depthFirstSearch(stack);
}
}
