Chức năng du lịch đệ quy đầu tiên trong Java hoặc C++?

Question

Đây là một mã java cho việc đi lại chiều rộng đầu tiên:

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

Có thể viết một hàm đệ quy để làm như vậy?

Lúc đầu, tôi nghĩ rằng điều này sẽ được dễ dàng, vì vậy tôi bước ra với điều này:

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

Sau đó, tôi tìm thấy nó không hoạt động. Nó thực sự giống như thế này:

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

Có ai từng nghĩ về điều này trước đây không?

Answer 1

Tôi không thể tưởng tượng tại sao bạn muốn, khi bạn có một giải pháp lặp đi lặp lại một cách hoàn hảo tốt, nhưng ở đây bạn đi;)

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) 

tôi nên thêm rằng nếu bạn thực sự muốn đi qua các nút của cây một cách đệ quy, sau đó bạn có thể làm một DFS với tham số level và các nút đầu ra chỉ tại level, sau đó recurse lên. Nhưng đó chỉ là nói chuyện điên rồ, bởi vì bạn muốn xem lại các nút một cách quá nhiều lần ... Chỉ cần chấp nhận rằng BFS là một thuật toán lặp lại. :)

Answer 2

Thuật toán BFS không phải là thuật toán đệ quy (trái ngược với DFS).

Một có thể thử viết hàm đệ quy mô phỏng thuật toán nhưng điều đó sẽ kết thúc khá nhanh. Điều gì sẽ là điểm trong việc này?

Answer 3

Bạn có thể sử dụng iterative deepening depth-first search, đây là thuật toán hiệu quả đầu tiên sử dụng đệ quy. Nó thậm chí còn tốt hơn BFS nếu bạn có một yếu tố phân nhánh cao, vì nó không sử dụng nhiều bộ nhớ.

Answer 4

Điều này sẽ không thỏa mãn với mọi người - tôi chắc chắn. Với tất cả sự tôn trọng mọi người. Đối với những người hỏi điểm là gì? Vấn đề là chúng tôi tin rằng mọi thuật toán lặp lại cũng có một giải pháp đệ quy (dễ)? Đây là giải pháp của "sisis" từ stackoverflow.

BFS(Q) 

{ 

    if (|Q| > 0) 

    v < - Dequeue(Q) 

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

    BFS(Q) 
} 

Nó có số tiền thú vị nhất định trong đó, nhưng không rõ rằng nó vi phạm bất kỳ quy tắc đệ quy nào. Nếu nó không vi phạm bất kỳ quy tắc đệ quy nào, thì nó phải được chấp nhận. IMHO.

Answer 5

Truy vấn BFS và DFS đơn giản: Chỉ cần đẩy/cung cấp nút gốc của cây trong ngăn xếp/xếp hàng và gọi các chức năng này!

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

}