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

Is it possible to write a recursive function to do the same?

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

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

以前有人考虑过这个吗？

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)

我应该补充一点，如果你真的想递归地遍历树的节点，那么您可以使用 level 参数执行 DFS，并仅在 level 输出节点，然后向上递归。但这只是疯狂的言论，因为你会多次重新访问节点......只要接受 BFS 是一种迭代算法即可。 :)

Answer 2

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

人们可以尝试编写一个递归函数来模拟该算法，但这最终会变得相当奇怪。这样做有什么意义呢？

Answer 3

您可以使用迭代加深深度优先搜索，它实际上是一种广度优先算法使用递归。如果分支因子较高，它甚至比 BFS 更好，因为它不使用太多内存。

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

}

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

Answer 6

这不会让每个人都满意——我确信。谨向大家致以崇高敬意。对于那些问这有什么意义的人？关键是我们相信每个迭代算法都有一个（简单？）递归解决方案。
这是 stackoverflow 中“sisis”的解决方案。

BFS(Q)

{

  if (|Q| > 0) 

     v < - Dequeue(Q)

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

     BFS(Q)
}

它有一定的有趣之处，但不清楚它是否违反了任何递归规则。如果它不违反任何递归规则，那么它应该被接受。恕我直言。