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

algorithm java tree c++ breadth-first-search

2022-09-02 23:24:29

下面是一个用于广度优先旅行的 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);
}

以前有没有想过这个问题？

答案 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，并且只在处输出节点，然后递归。但这只是疯狂的谈话，因为你会多次重新审视节点......只要接受BFS是一种迭代算法。:)levellevel

答案 2

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

人们可以尝试编写一个模拟算法的递归函数，但这最终会非常奇怪。这样做有什么意义？