Ricorsiva funzione di viaggio di ampiezza in Java o C++?

Question

Qui è un codice Java per i viaggi in ampiezza:

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

E 'possibile scrivere una funzione ricorsiva di fare lo stesso?

In un primo momento, ho pensato che questo sarebbe stato facile, così sono uscito con questo:

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

poi ho scoperto che non funziona. In realtà fa la stessa cosa:

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

Qualcuno ha pensato a questo prima?

Answer 1

non riesco a immaginare il motivo per cui ci si vuole, quando si ha una perfetta buona soluzione iterativa, ma qui si va;)

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) 

Vorrei aggiungere che se si vuole veramente per attraversare i nodi dell'albero in modo ricorsivo, quindi è possibile eseguire un DFS con un parametro level e restituire i nodi solo a level, quindi ricorrere nuovamente. Ma è solo una chiacchiera pazzesca, perché dovresti rivedere i nodi wayyyyy troppe volte ... Accetta solo che BFS sia un algoritmo iterativo. :)

Answer 2

L'algoritmo BFS non è un algoritmo ricorsivo (al contrario di DFS).

Uno potrebbe provare a scrivere una funzione ricorsiva che emula l'algoritmo ma che finirebbe abbastanza bizzarro. Quale sarebbe il punto nel fare questo?

Answer 3

È possibile utilizzare iterative deepening depth-first search, che è effettivamente un algoritmo di ampiezza che utilizza la ricorsione. È anche meglio di BFS se hai un elevato fattore di ramificazione, dato che non usa molta memoria.

Answer 4

Questo non sarà soddisfacente per tutti, ne sono sicuro. Con tutto il rispetto per tutti. Alle persone che chiedono qual è il punto? Il punto è che crediamo che ogni algoritmo iterativo abbia anche una soluzione ricorsiva (facile?). Ecco una soluzione di "sisis" da stackoverflow.

BFS(Q) 

{ 

    if (|Q| > 0) 

    v < - Dequeue(Q) 

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

    BFS(Q) 
} 

Ha certa quantità di funninest in essa, ma non è chiaro che esso viola tutte le regole ricorsive. Se non viola alcuna regola ricorsiva, allora dovrebbe essere accettata. A PARER MIO.

Answer 5

A BFS semplice e ricorsione DFS: basta premere/offrono il nodo radice di albero in pila/coda e chiamano queste funzioni!

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

}