Java或C ++中的递归广度优先旅行函数？
这是一个广度优先旅行的java代码：
void breadthFirstNonRecursive(){ Queue queue = new java.util.LinkedList(); 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); } } 是否可以编写递归函数来做同样的事情？
起初，我认为这很容易，所以我出来了：
void breadthFirstRecursive(){ Queue q = new LinkedList(); breadthFirst(root, q); } void breadthFirst(Node node, Queue 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); }
然后我发现它不起作用。 它实际上与此相同：
void preOrder(Node node) { if (node == null) return; visit(node); preOrder(node.left); preOrder(node.right); }
有没有人想过这个？
当你有一个非常好的迭代解决方案时，我无法想象你为什么要这样，但是你走了;）
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)
我应该补充一点，如果你真的想以递归方式遍历树的节点，那么你可以用一个level参数做一个DFS，只在level输出节点，然后再递增。 但这只是疯狂的谈话，因为你多次重新访问节点…只是接受BFS是一种迭代算法。 🙂
BFS算法不是递归算法（与DFS相反）。
人们可以尝试编写一个模拟算法的递归函数，但最终会变得非常古怪。 这样做有什么意义？
您可以使用迭代深化深度优先搜索 ，这实际上是使用递归的广度优先算法。 如果你有一个很高的分支因子，它甚至比BFS更好，因为它不会占用太多内存。
这对所有人来说都不会令人满意 – 我相信。 尊重每个人。 对于那些问有什么意义的人？ 关键是我们相信每个迭代算法都有一个（简单的）递归解决方案。 这是来自stackoverflow的“sisis”的解决方案。
BFS(Q) { if (|Q| > 0) v < - Dequeue(Q) Traverse(v) foreach w in children(v) Enqueue(Q, w) BFS(Q) }
它有一定的趣味性，但不清楚它是否违反了任何递归规则。 如果它没有违反任何递归规则，那么它应该被接受。 恕我直言。
一个简单的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);
}