Рекурсивная функция перемещения в ширину в Java или C ++?

Question

Вот код 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);
}

Кто-нибудь думал об этом раньше?

Answer 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 с параметром level и вывести узлы только при level, а затем выполнить возврат. Но это просто сумасшедший разговор, потому что вы бы слишком много раз посещали узлы wayyyyy ... Просто примите, что BFS - это итеративный алгоритм. :)

Answer 2

Алгоритм BFS не является рекурсивным алгоритмом (в отличие от DFS).

Один может попытаться написать рекурсивную функцию, которая эмулирует алгоритм, но в итоге это будет довольно странно. Какой смысл делать это?

Answer 3

Вы можете использовать итеративное углубление поиска в глубину , который по сути является алгоритмом в ширину и использует рекурсию Это даже лучше, чем BFS, если у вас высокий коэффициент ветвления, так как он не использует много памяти.

Answer 4

Простая рекурсия BFS и DFS: Просто нажмите / предложите корневой узел дерева в стеке / очереди и вызовите эти функции!

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

}

Answer 5

Это не будет удовлетворять всех - я уверен. При всем уважении к каждому. Людям, которые спрашивают, в чем смысл? Дело в том, что мы считаем, что каждый итерационный алгоритм также имеет (простое?) Рекурсивное решение. Вот решение "sisis" из stackoverflow.

BFS(Q)

{

  if (|Q| > 0) 

     v < - Dequeue(Q)

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

     BFS(Q)
}

В нем есть определенное количество смешного, но не ясно, что оно нарушает какие-либо рекурсивные правила. Если это не нарушает какие-либо рекурсивные правила, то оно должно быть принято. ИМХО.