Java或C++中的递归广度优先旅行函数？

下面是广度优先行程的Java代码：Java或C++中的递归广度优先旅行函数？

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

以前有没有想过这个？

来源

2010-06-03 joejax

顺便说一句，做BFS递归可能会导致你的筹码在状态空间的大小增长。如果您的解决方案处于深度d，则找到解决方案所需的堆栈空间为b^d，其中b为分支因子。 – Eric 2010-06-25 17:23:06

我无法想象为什么你会想，当你有一个完美的迭代求解，但在这里，你去;）

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，然后递增。但这只是一个疯狂的话题，因为你会重复访问节点wayyyyy太多次了......只要接受BFS是一个迭代算法。 :)

来源

2010-06-03 19:23:14 Stephen

DFS-with-a-level实际上并不是那么糟糕的主意 - 它被称为迭代加深深度优先搜索，非常方便。看我的帖子。 – gustafc 2010-06-03 20:01:02

@gustafc，谢谢，是的我意识到迭代加深，我应该引用它。我没有意识到这只是11％的节点访问税，这是令人惊讶的。 – Stephen 2010-06-03 20:38:41

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

其中一个可能尝试编写一个模拟算法的递归函数，但最终会相当混乱。这样做的意义何在？

来源

2010-06-03 19:23:19 ob1

您可以使用iterative deepening depth-first search，它实际上是使用递归的广度优先算法。如果你有很高的分支因子，它比BFS更好，因为它不占用太多内存。

来源

2010-06-03 19:58:13 gustafc

这是迄今为止最好的答案。 – 2014-11-14 18:06:04

这不会令所有人满意，我相信。尊重每个人。对于那些问问题的人来说呢？重点是我们相信每个迭代算法都有一个（简单的）递归解决方案。以下是由stackoverflow中的“sisis”提供的解决方案。

BFS(Q) 

{ 

    if (|Q| > 0) 

    v < - Dequeue(Q) 

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

    BFS(Q) 
}

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

来源

2013-02-26 21:03:40 jim

一个简单的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-04 01:21:23

Java或C++中的递归广度优先旅行函数？

回答

相关问题