Thứ tự cấp độ cây nhị phân truyền ngang

Question

Ba loại traversals cây theo thứ tự, đặt hàng trước và thứ tự bài đăng.

Lượt truy cập thứ tư, ít được sử dụng hơn, truyền tải là truyền tải cấp bậc. Trong một traverses cấp bậc , tất cả các nút ở độ sâu "d" được xử lý trước bất kỳ nút nào ở độ sâu d + 1. Traversal cấp bậc khác với các lần truy cập khác ở chỗ nó không được thực hiện đệ quy; một hàng đợi được sử dụng, thay vì ngăn xếp ngụ ý của đệ quy.

Câu hỏi của tôi trên đoạn văn bản trên là

1. Tại sao traversals trật tự mức độ không được thực hiện một cách đệ quy?
2. Hàng đợi được sử dụng như thế nào trong quá trình truyền tải thứ tự cấp? Yêu cầu làm rõ bằng mã Pseudo sẽ hữu ích.

Cảm ơn!

Answer 1

Level order traversal thực sự là một BFS, không phải là đệ quy một cách tự nhiên. Nó sử dụng Queue thay vì Stack để giữ các đỉnh tiếp theo sẽ được mở. Lý do cho nó là trong traversal này, bạn muốn mở các nút trong một đơn đặt hàng FIFO, thay vì một đơn đặt hàng LIFO, thu được bằng cách đệ quy

như thứ tự cấp thực sự là một BFS và [BFS] của nó mã giả [lấy từ wikipedia] là:

1 procedure BFS(Graph,source): 
2  create a queue Q 
3  enqueue source onto Q 
4  mark source 
5  while Q is not empty: 
6   dequeue an item from Q into v 
7   for each edge e incident on v in Graph: 
8    let w be the other end of e 
9    if w is not marked: 
10     mark w 
11     enqueue w onto Q 

(*) trong cây, đánh dấu các đỉnh là không cần thiết, vì bạn không thể vào cùng một nút trong 2 đường dẫn khác nhau.

Answer 2

Bạn sẽ tìm thấy tổng quan tốt trong Wikipedia ngay cả với đoạn mã.

Answer 3

void levelorder(Node *n) 
{ queue < Node * >q; 

    q.push(n); 


    while(!q.empty()) 
    { 
      Node *node = q.front(); 
      cout<<node->value; 
      q.pop(); 
      if(node->left != NULL) 
      q.push(node->left); 
      if (node->right != NULL) 
      q.push(node->right); 

    } 

} 

Answer 4

Thay vì hàng đợi, tôi đã sử dụng bản đồ để giải quyết vấn đề này. Hãy xem, nếu bạn quan tâm. Như tôi đã làm một traversal postorder, tôi duy trì độ sâu mà tại đó mỗi nút được bố trí và sử dụng độ sâu này là chìa khóa trong một bản đồ để thu thập các giá trị trong cùng cấp

class Solution { public: map<int, vector<int> > levelValues; void recursivePrint(TreeNode *root, int depth){ if(root == NULL) return; if(levelValues.count(root->val) == 0) levelValues.insert(make_pair(depth, vector<int>())); levelValues[depth].push_back(root->val); recursivePrint(root->left, depth+1); recursivePrint(root->right, depth+1); } vector<vector<int> > levelOrder(TreeNode *root) { recursivePrint(root, 1); vector<vector<int> > result; for(map<int,vector<int> >::iterator it = levelValues.begin(); it!= levelValues.end(); ++it){ result.push_back(it->second); } return result; } };

Toàn bộ giải pháp có thể được tìm thấy ở đây - http://ideone.com/zFMGKU Giải pháp trả về một vec tơ vectơ với mỗi vectơ bên trong chứa các phần tử trong cây theo đúng thứ tự.

bạn có thể thử giải quyết nó ở đây - https://oj.leetcode.com/problems/binary-tree-level-order-traversal/

Và, như bạn có thể thấy, chúng tôi cũng có thể làm điều này một cách đệ quy trong cùng một thời gian và phức tạp không gian là giải pháp hàng đợi!

Answer 5

https://github.com/arun2pratap/data-structure/blob/master/src/main/java/com/ds/tree/binarytree/BinaryTree.java

để hoàn thành có thể tìm ra liên kết ở trên.

public void levelOrderTreeTraversal(List<Node<T>> nodes){ 
    if(nodes == null || nodes.isEmpty()){ 
     return; 
    } 
    List<Node<T>> levelNodes = new ArrayList<>(); 
    nodes.stream().forEach(node -> { 
     if(node != null) { 
      System.out.print(" " + node.value); 
      levelNodes.add(node.left); 
      levelNodes.add(node.right); 
     } 
    }); 
    System.out.println(""); 
    levelOrderTreeTraversal(levelNodes); 
} 

Cũng có thể kiểm tra http://www.geeksforgeeks.org/

đây bạn sẽ tìm thấy câu trả lời liên quan Hầu hết các cấu trúc dữ liệu.