16

这是广度优先旅行的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);
}

有没有人考虑过这个？

4

6 回答 6

21

我无法想象你为什么想要，当你有一个非常好的迭代解决方案时，但是你去；）

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 是一种迭代算法即可。:)

于 2010-06-03T19:23:14.763 回答
12

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

可以尝试编写一个模拟算法的递归函数，但结果会很奇怪。这样做有什么意义？

于 2010-06-03T19:23:19.677 回答
9

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

于 2010-06-03T19:58:13.647 回答
1

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

}

于 2015-05-04T01:21:23.890 回答
1

这是一个使用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);
             }
        }
于 2021-10-15T01:05:22.580 回答
0

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

BFS(Q)

{

  if (|Q| > 0) 

     v < - Dequeue(Q)

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

     BFS(Q)
}

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

于 2013-02-26T21:03:40.127 回答