Fonction récursive de première largeur en Java ou en C++?

Question

Voici un code java pour Voyage en largeur:

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

Est-il possible d'écrire une fonction récursive pour faire la même chose?

Au début, je pensais que ce serait facile, alors je suis venu avec ceci:

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

Je trouve cela ne fonctionne pas. Il fait en fait la même chose que ceci:

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

Avez-vous déjà pensé à cela?

Answer 1

Je ne peux pas imaginer pourquoi vous voudriez, quand vous avez une très bonne solution itérative, mais ici vous allez;)

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) 

Je dois ajouter que si vous voulez vraiment traverser les nœuds de l'arborescence récursivement, alors vous pouvez faire un DFS avec un paramètre level, et des nœuds de sortie seulement à level, puis récursif. Mais c'est juste une discussion folle, parce que vous reviendrez les nœuds wayyyyy trop de fois ... Acceptez simplement que BFS est un algorithme itératif. :)

Answer 2

L'algorithme BFS n'est pas un algorithme récursif (par opposition à DFS).

Un pourrait essayer d'écrire une fonction récursive qui émule l'algorithme mais qui finirait par être assez bizzare. Quel serait le but de faire cela?

Answer 3

Vous pouvez utiliser iterative deepening depth-first search, qui est en réalité un algorithme de première grandeur utilisant la récursivité. C'est encore mieux que BFS si vous avez un facteur de branchement élevé, car il n'utilise pas beaucoup de mémoire.

Answer 4

Cela ne va pas être satisfaisant pour tout le monde - j'en suis sûr. Avec tout le respect pour tout le monde. Aux personnes qui demandent quel est le point? Le fait est que nous croyons que chaque algorithme itératif a aussi une solution récursive (facile?). Voici une solution de "sisis" de stackoverflow.

BFS(Q) 

{ 

    if (|Q| > 0) 

    v < - Dequeue(Q) 

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

    BFS(Q) 
} 

Il a une certaine quantité de funninest en elle, mais il ne sait pas qu'il ne viole aucune règle récursives. S'il ne viole aucune règle récursive, alors il devrait être accepté. A MON HUMBLE AVIS.

Answer 5

Une récursion BFS et DFS simple: Il vous suffit d'appuyer sur/d'offrir le nœud racine de l'arbre dans la pile/queue et d'appeler ces fonctions!

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

}