ทำให้เป็นอันดับและดีซีเรียลไลซ์ N-ary Tree ใน C++

สมมติว่าเรามีต้นไม้ N-ary หนึ่งต้น และเราต้องทำให้เป็นอนุกรมและดีซีเรียลไลซ์ต้นไม้เหล่านั้น ดังที่เราทราบดีว่าการทำให้เป็นอนุกรมเป็นกระบวนการของการแปลงโครงสร้างข้อมูลหรืออ็อบเจ็กต์เป็นลำดับของบิต เพื่อให้เราสามารถเก็บไว้ในไฟล์หรือบัฟเฟอร์หน่วยความจำ และสามารถสร้างใหม่ได้ในภายหลังในสภาพแวดล้อมเดียวกันหรือคอมพิวเตอร์อื่น

ที่นี่เราต้องสร้างอัลกอริทึมเพื่อทำให้เป็นอนุกรมและดีซีเรียลไลซ์ทรี N-ary ต้นไม้ N-ary เป็นต้นไม้ที่รูทแล้ว ซึ่งแต่ละโหนดมีลูกไม่เกิน N

ดังนั้นหากอินพุตเป็นแบบ

จากนั้นผลลัพธ์จะเป็น Serialize:1 #3 2 4 #5 6 ##### และ Deserialized Tree:1[3[5, 6, ], 2, 4, ]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน createVector() ซึ่งจะใช้เวลา s

• กำหนดอาร์เรย์ 2D ret หนึ่งรายการ

• กำหนดอาร์เรย์ tempv

• temp :=สตริงว่าง

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • ถ้า s[i] ไม่เท่ากับช่องว่าง และ s[i] ไม่เท่ากับ '#' ดังนั้น −

    • temp :=temp + s[i]

  • มิฉะนั้นเมื่อ s[i] เหมือนกับสตริงว่าง ดังนั้น −

    • ใส่จำนวนเต็ม temp s ที่ส่วนท้ายของ tempv

    • temp :=สตริงว่าง

  • มิฉะนั้นเมื่อ s[i] เหมือนกับ '#' ดังนั้น −

    • ใส่ tempv ที่ส่วนท้ายของ ret

    • temp :=สตริงว่าง

    • อุณหภูมิที่ชัดเจน

• ในขณะที่ (ไม่ ret ว่างเปล่าและองค์ประกอบสุดท้ายของ ret เหมือนกับ 0) ทำ -

  • ลบองค์ประกอบสุดท้ายออกจาก ret

• รีเทิร์น

• กำหนดฟังก์ชัน serialize() ซึ่งจะทำการรูท

• ret :=สตริงว่าง

• ถ้าไม่ใช่รูทก็ไม่ใช่ศูนย์ ดังนั้น −

  • รีเทิร์น

• กำหนดหนึ่งคิว q

• แทรกรูทลงใน q

• rret :=ret concatenate val ของรูท

• ret :=ret ต่อช่องว่าง

• ret :=ret concatenate "#"

• ในขณะที่ (ไม่ใช่ q ว่างเปล่า) ทำ -

  • curr =องค์ประกอบแรกของ q

  • ลบองค์ประกอบออกจาก q

  • สำหรับการเริ่มต้น i :=0 เมื่อฉัน <ขนาดของอาร์เรย์ลูกของ curr ให้อัปเดต (เพิ่ม i โดย 1) ทำ -

    • ถ้าลูก[i] ของเคอร์ แล้ว −

      • ret :=ret concatenate children[i] ของสกุลเงิน

      • ใส่ลูก[i] ของcurr ลงใน q

    • ret :=ret + สตริงว่าง

  • ret :=ret concatenate "#"

• รีเทิร์น

• กำหนดฟังก์ชัน deserialize() ซึ่งจะใช้ข้อมูล

• ถ้าขนาดของข้อมูลเท่ากับ 0 แล้ว −

  • คืนค่า null

• กำหนดอาร์เรย์ 2 มิติ v :=createVector(data)

• ret :=โหนดใหม่ที่มีค่า v[0, 0]

• กำหนดหนึ่งคิว q

• แทรก ret ลงใน q

• ผม :=1

• ในขณะที่ (ไม่ใช่ q ว่างเปล่าและฉัน − ขนาดของ v) ทำ −

  • curr =องค์ประกอบแรกของ q

  • ลบองค์ประกอบออกจาก q

  • สำหรับการเริ่มต้น j :=0 เมื่อ j − ขนาดของ v[i] ให้อัปเดต (เพิ่ม j ทีละ 1) ให้ทำ −

    • โหนด :=v[i, j]

    • temp =โหนดใหม่พร้อมโหนดค่า

    • ใส่ temp ที่ส่วนท้ายของลูกของ curr

    • ใส่อุณหภูมิลงใน q

  • (เพิ่ม i ขึ้น 1)

• รีเทิร์น

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
class Node {
public:
   int val;
   vector<Node*> children;
   Node() {}
   Node(int _val) {
      val = _val;
   }
   Node(int _val, vector<Node*> _children) {
      val = _val;
      children = _children;
   }
};
string n_ary_to_str(Node *root){
   string ret = "";
   if(root){
      ret = ret + to_string(root->val);
      if(root->children.size() > 0){
         ret += "[";
         for(Node* child : root->children){
            ret += n_ary_to_str(child) + ", ";
         }
         ret += "]";
      }
   }
   return ret;
}
class Codec {
public:
   vector<vector<int>>createVector(string s) {
      vector<vector<int>> ret;
      vector<int> tempv;
      string temp = "";
      for (int i = 0; i < s.size(); i++) {
         if (s[i] != ' ' && s[i] != '#') {
            temp += s[i];
         }
         else if (s[i] == ' ') {
            tempv.push_back(stoi(temp));
            temp = "";
         }
         else if (s[i] == '#') {
            ret.push_back(tempv);
            temp = "";
            tempv.clear();
         }
      }
      while (!ret.empty() && ret.back().size() == 0)
      ret.pop_back();
      return ret;
   }
   string serialize(Node *root) {
      string ret = "";
      if (!root)
         return ret;
      queue<Node *> q;
      q.push(root);
      ret += to_string(root->val);
      ret += " ";
      ret += "#";
      while (!q.empty()) {
         Node *curr = q.front();
         q.pop();
         for (int i = 0; i < curr->children.size(); i++) {
            if (curr->children[i]) {
               ret += to_string(curr->children[i]->val);
               q.push(curr->children[i]);
            }
            ret += " ";
         }
         ret += "#";
      }
      return ret;
   }
   Node *deserialize(string data) {
      Node *ret;
      if (data.size() == 0)
         return NULL;
         vector<vector<int>> v = createVector(data);
         ret = new Node(v[0][0]);
         queue<Node *> q;
         q.push(ret);
         int i = 1;
         while (!q.empty() && i < v.size()) {
            Node *curr = q.front();
            q.pop();
            for (int j = 0; j < v[i].size(); j++) {
               int node = v[i][j];
                  Node *temp = new Node(node);
                  curr->children.push_back(temp);
                  q.push(temp);
               }
               i++;
            }
            return ret;
         }
 };
main() {
   Codec ob;
   Node n5(5), n6(6);
   Node n3(3); n3.children.push_back(&n5); n3.children.push_back(&n6);
   Node n2(2), n4(4);
   Node n1(1); n1.children.push_back(&n3); n1.children.push_back(&n2);
   n1.children.push_back(&n4);
   cout << "Given Tree: " << n_ary_to_str(&n1) << endl;
   string ser = ob.serialize(&n1);
   cout << "Serialize: " << ser << endl;
   Node *deser = ob.deserialize(ser);
   cout << "Deserialized Tree: " << n_ary_to_str(deser);
}

อินพุต

Node n5(5), n6(6);
Node n3(3); n3.children.push_back(&n5); n3.children.push_back(&n6);
Node n2(2), n4(4);
Node n1(1); n1.children.push_back(&n3); n1.children.push_back(&n2);
n1.children.push_back(&n4);

ผลลัพธ์

Given Tree: 1[3[5, 6, ], 2, 4, ]
Serialize: 1 #3 2 4 #5 6 #####
Deserialized Tree: 1[3[5, 6, ], 2, 4, ]