Giao dịch thứ tự cấp độ cây N-ary trong C ++

Giả sử chúng ta có một cây n-ary, chúng ta phải trả về truyền tải thứ tự cấp của các giá trị của các nút của nó. Việc tuần tự hóa đầu vào Nary-Tree được biểu diễn theo trình tự cấp của chúng. Ở đây mỗi nhóm con được phân tách bằng giá trị null (Xem ví dụ). Vì vậy, cây sau có thể được biểu diễn là [1, null, 3,2,4, null, 5,6]

Đầu ra sẽ là [[1], [3,2,4], [5,6]]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• tạo một ma trận ans

• nếu root là null, trả về ans

• tạo một hàng đợi q và chèn thư mục gốc

• trong khi q không trống

  • size:=kích thước của hàng đợi

  • tạo một mảng tạm thời

  • trong khi kích thước không phải là 0

    • curr:=phần tử đầu tiên của q

    • chèn giá trị của curr vào temp

    • xóa phần tử khỏi hàng đợi

    • cho tôi trong phạm vi từ 0 đến kích thước của trẻ em của curr

      • chèn con thứ i của curr

    • giảm kích thước đi 1

  • chèn tạm thời vào ans

• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
class Node {
   public:
   int val;
   vector<Node*> children;
   Node() {}
   Node(int _val) {
      val = _val;
   }
   Node(int _val, vector<Node*> _children) {
      val = _val;
      children = _children;
   }
};
class Solution {
   public:
   vector<vector<int>> levelOrder(Node* root) {
      vector < vector <int> > ans;
      if(!root)return ans;
         queue <Node*> q;
      q.push(root);
      while(!q.empty()){
         int sz = q.size();
         vector<int> temp;
         while(sz--){
            Node* curr = q.front();
            temp.push_back(curr->val);
            q.pop();
            for(int i = 0; i < curr->children.size(); i++){
               q.push(curr->children[i]);
            }
         }
         ans.push_back(temp);
      }
      return ans;
   }
};
main(){
   Node *root = new Node(1);
   Node *left_ch = new Node(3), *mid_ch = new Node(2), *right_ch = new Node(4);
   left_ch->children.push_back(new Node(5));
   left_ch->children.push_back(new Node(6));
   root->children.push_back(left_ch);
   root->children.push_back(mid_ch);
   root->children.push_back(right_ch);
   Solution ob;
   print_vector(ob.levelOrder(root));
}

Đầu vào

[1,null,3,2,4,null,5,6]

Đầu ra

[[1, ],[3, 2, 4, ],[5, 6, ],]