Rekursive Breite-erste Reisefunktion in Java oder C++?

Question

Hier ist ein Java-Code für Breiten first travel:

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

Ist es möglich, eine rekursive Funktion zu schreiben, das gleiche zu tun?

Zuerst dachte ich, das einfach sein würde, so kam ich mit diesem aus:

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

Dann fand ich es nicht funktioniert. Es ist tatsächlich das Gleiche wie das:

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

Hat jemand darüber nachgedacht?

Answer 1

Ich kann nicht vorstellen, warum Sie wollen würde, wenn Sie eine ganz gute iterative Lösung, aber hier geht;)

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) 

Ich sollte hinzufügen, dass, wenn Sie wirklich wollen, zu durchqueren die Knoten des Baumes rekursiv, dann könnten Sie ein DFS mit einem level Parameter tun und Knoten nur bei level ausgeben, dann recurse up. Aber das ist nur verrückt reden, weil Sie Knoten wayyyyy zu oft wieder besuchen würden ... einfach akzeptieren, dass BFS ist ein iterativer Algorithmus. :)

Answer 2

Der BFS-Algorithmus ist kein rekursiver Algorithmus (im Gegensatz zu DFS).

Ein könnte versuchen, eine rekursive Funktion zu schreiben, die den Algorithmus emuliert, aber das würde ziemlich bizzare enden. Was wäre der Sinn dafür?

Answer 3

Sie können iterative deepening depth-first search verwenden, was effektiv ein Breast-First-Algorithmus ist, der Rekursion verwendet. Es ist sogar besser als BFS, wenn Sie einen hohen Verzweigungsfaktor haben, da es nicht viel Speicher verbraucht.

Answer 4

Dies wird nicht für alle befriedigend sein - da bin ich mir sicher. Mit allem Respekt für alle. Um die Leute, die fragen, was ist der Sinn? Der Punkt ist, dass wir glauben, dass jeder iterative Algorithmus auch eine (einfache?) Rekursive Lösung hat. Hier ist eine Lösung von "sisis" von stackoverflow.

BFS(Q) 

{ 

    if (|Q| > 0) 

    v < - Dequeue(Q) 

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

    BFS(Q) 
} 

Es hat gewisse funninest drin, aber es ist nicht klar, dass es keine rekursiven Regeln verstößt. Wenn es keine rekursiven Regeln verletzt, sollte es akzeptiert werden. MEINER BESCHEIDENEN MEINUNG NACH.

Answer 5

Eine einfache BFS und DFS Rekursion: Drücken Sie einfach/bieten Sie den Stammknoten des Baumes in Stack/Queue und rufen Sie diese Funktionen!

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

}