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

有没有人想过这个？

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更好,因为它不会占用太多内存.