¿Función de viaje de amplitud recursiva en Java o C++?

Question

Aquí es un código java para el recorrido primero en amplitud:

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

¿Es posible escribir una función recursiva para hacer lo mismo?

Al principio, pensé que esto sería fácil, así que salió con esto:

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

Entonces me encontré con que no funciona. En realidad, hace lo mismo que esto:

void preOrder(Node node) { 
    if (node == null) return; 
    visit(node); 
    preOrder(node.left); 
    preOrder(node.right); 
} 

¿Alguien ha pensado en esto antes?

Answer 1

no puedo imaginar por qué que te gustaría, cuando se tiene un perfectamente buena solución iterativa, pero aquí tienes;)

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) 

debo añadir que si realmente quiere realizar el desplazamiento los nodos del árbol de forma recursiva, entonces podría hacer un DFS con un parámetro level, y los nodos de salida solo en level, luego recular arriba. Pero eso es solo una locura, porque volverías a visitar nodos muchas veces ... Solo acepta que BFS es un algoritmo iterativo. :)

Answer 2

El algoritmo BFS no es un algoritmo recursivo (en contraposición a DFS).

Uno podría intentar escribir una función recursiva que emule el algoritmo pero que terminaría siendo bastante extraño. ¿Cuál sería el sentido de hacer esto?

Answer 3

Puede utilizar iterative deepening depth-first search, lo que efectivamente es un algoritmo primero en amplitud que utiliza la recursividad. Es incluso mejor que BFS si tiene un alto factor de ramificación, ya que no usa mucha memoria.

Answer 4

Esto no va a ser satisfactorio para todos, estoy seguro. Con todo respeto para todos. A las personas que preguntan cuál es el punto? El punto es que creemos que cada algoritmo iterativo tiene también una solución recursiva (¿fácil?). Aquí hay una solución de "sisis" de stackoverflow.

BFS(Q) 

{ 

    if (|Q| > 0) 

    v < - Dequeue(Q) 

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

    BFS(Q) 
} 

Tiene cierta cantidad de funninest en ella, pero no está claro de que viola las reglas recursivas. Si no viola ninguna regla recursiva, entonces debe ser aceptada. EN MI HUMILDE OPINIÓN.

Answer 5

Un BFS simple y recursividad DFS: Just Push/ofrecen el nodo raíz del árbol en pila/cola y llamar a estas funciones!

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

}