在Java或C ++中递归实现广度优先遍历函数？

Question

这是一段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);
    }
}

是否可以编写一个递归函数来完成相同的功能？

起初，我认为这很容易，所以想到了这个：

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);   
}

后来我发现它不起作用。实际上它所做的事情与这个相同:

void preOrder(Node node) {
    if (node == null) return;
    visit(node);
    preOrder(node.left);
    preOrder(node.right);
}

有没有人之前考虑过这个问题？

- joejax

---

顺便提一下，递归地执行BFS可能会导致堆栈大小增长到状态空间的大小。如果您的解决方案在深度d处，则查找解决方案所需的堆栈空间将为b^d，其中b是分支因子。 - Eric

Answer 1

虽然我无法想象你为什么想这么做，因为你已经有了一个完美的迭代解决方案，但是这里给出实现方法；）

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)

我应该补充说，如果你真的想以递归方式遍历树的节点，那么你可以使用深度优先搜索（DFS）和一个level参数，并仅在level上输出节点，然后向上递归。但是这很疯狂，因为你会重复访问太多次节点……只要接受BFS是一种迭代算法就好了 :)

- Stephen

---

DFS-with-a-level 其实并不是一个坏主意——它被称为迭代加深深度优先搜索，非常方便。请参阅我的帖子。 - gustafc

@gustafc，谢谢，是的，我知道迭代加深搜索，我应该引用它。我没有意识到它只是节点访问的11％税，这很令人惊讶。 - Stephen

Answer 2

BFS算法不是递归算法（与DFS相反）。

有人可以尝试编写一个模拟该算法的递归函数，但这会变得非常奇怪。那么这么做有什么意义呢？

- ob1

---

针对编程面试。我知道有些公司会要求使用递归BFS解决问题。唉！ - prashant

Answer 3

你可以使用迭代加深深度优先搜索，它有效地是一种使用递归的广度优先算法。如果你有一个高分支因子，它甚至比BFS更好，因为它不占用太多内存。

- gustafc

---

这绝对是这里最好的答案。 - John G

Answer 4

一个简单的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);

}

- ThePatelGuy

Answer 5

这里有一个使用ArrayList而不是队列的示例，我预定义了邻接矩阵和访问数组。同时创建了边。

    public void BFS(int node, boolean[]visited)
        {
         List<Integer> li=new ArrayList<>();
         for(int j:adj[node])
         {
           if(!visited[j])
             {
                 System.out.println(j+" ");
                 visited[j]=true;
                 li.add(j);
             }
         }
             for(int j:li){
                 BFS(j,visited);
             }
        }

- Sneha Ravichandran

Answer 6

这并不会让每个人都满意，我相信。对于每个人都表示尊重。对于那些问“有什么意义”的人来说，我们认为每个迭代算法也有一个（简单的？）递归解决方案。

以下是stackoverflow用户“sisis”提供的解决方案。

BFS(Q)

{

  if (|Q| > 0) 

     v < - Dequeue(Q)

     Traverse(v)
     foreach w in children(v)
        Enqueue(Q, w)    

     BFS(Q)
}

它有一定的趣味性，但不清楚它是否违反了任何递归规则。如果它没有违反任何递归规则，那么它应该被接受。在我看来。

- jim