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

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

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

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

จากนั้นผลลัพธ์จะเป็น Serialize − 1 2 3 4 5 N N N N N N ต้นไม้ดีซีเรียลไลซ์:4 2 5 1 3

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

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

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

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

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

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

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

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

  • หากไม่มีสกุลเงิน −

    • ret :=ret เชื่อม "N"

    • ret :=ret เชื่อมช่องว่าง

    • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

  • ret :=ret + มูลค่าของสกุลเงิน

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

  • ด้านซ้ายของเคอร์เซอร์ที่ส่วนท้ายของ q

  • ด้านขวาของสกุลเงินที่ส่วนท้ายของ q

• รีเทิร์น

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

• ถ้า data[0] เหมือนกับ 'N' แล้ว −

  • คืนค่า NULL

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

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

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

  • ถ้า data[i] เหมือนกับช่องว่าง ดังนั้น −

    • ใส่ temp ที่ท้าย v

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

    • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

  • temp :=temp + data[i]

• newRoot =โหนดใหม่พร้อม v[0]

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

• แทรก newRoot ลงใน q

• ผม :=1

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

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

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

  • ถ้า v[i] ไม่เท่ากับ "N" แล้ว −

    • left of parent :=โหนดใหม่พร้อม v[i]

    • แทรกด้านซ้ายของ parent ลงใน q

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

  • ถ้า v[i] ไม่เท่ากับ "N" แล้ว −

    • ด้านขวาของพาเรนต์ :=โหนดใหม่พร้อม v[i]

    • แทรกด้านขวาของ parent ลงใน q

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

• ส่งคืนรูทใหม่

ตัวอย่าง

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

#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data) {
      val = data;
      left = NULL;
      right = NULL;
   }
};
void insert(TreeNode **root, int val) {
   queue<TreeNode *> q;
   q.push(*root);
   while (q.size()) {
      TreeNode *temp = q.front();
      q.pop();
      if (!temp->left) {
         if (val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
      }
      else {
         q.push(temp->left);
      }
      if (!temp->right) {
         if (val != NULL)
            temp->right = new TreeNode(val);
         else
            temp->right = new TreeNode(0);
         return;
      }
      else {
         q.push(temp->right);
      }
   }
}
TreeNode *make_tree(vector<int> v) {
   TreeNode *root = new TreeNode(v[0]);
   for (int i = 1; i < v.size(); i++) {
      insert(&root, v[i]);
   }
   return root;
}
void inord(TreeNode *root) {
   if (root != NULL) {
      inord(root->left);
      cout << root->val << " ";
      inord(root->right);
   }
}
class Codec {
public:
   string serialize(TreeNode *root) {
      string ret = "";
      queue<TreeNode *> q;
      q.push(root);
      while (!q.empty()) {
         TreeNode *curr = q.front();
         q.pop();
         if (!curr) {
            ret += "N";
            ret += " ";
            continue;
         }
         ret += to_string(curr->val);
         ret += " ";
         q.push(curr->left);
         q.push(curr->right);
      }
      return ret;
   }
   TreeNode *deserialize(string data) {
      if (data[0] == 'N')
         return NULL;
      string temp = "";
      vector<string> v;
      for (int i = 0; i < data.size(); i++) {
         if (data[i] == ' ') {
            v.push_back(temp);
            temp = "";
            continue;
         }
         temp += data[i];
      }
      TreeNode *newRoot = new TreeNode(stoi(v[0]));
      queue<TreeNode *> q;
      q.push(newRoot);
      int i = 1;
      while (!q.empty() && i < v.size()) {
         TreeNode *parent = q.front();
         q.pop();
         if (v[i] != "N") {
            parent->left = new TreeNode(stoi(v[i]));
            q.push(parent->left);
         }
         i++;
         if (v[i] != "N") {
            parent->right = new TreeNode(stoi(v[i]));
            q.push(parent->right);
         }
         i++;
      }
      return newRoot;
   }
};
main() {
   Codec ob;
   vector<int> v = {1,2,3,4,5};
   TreeNode *root = make_tree(v);
   cout << "Given Tree: ";
   inord(root);
   cout << endl;
   string ser = ob.serialize(root);
   cout << "Serialize: " << ser << endl;
   TreeNode *deser = ob.deserialize(ser);
   cout << "Deserialized Tree: ";
   inord(root);
}

อินพุต

1,2,3,4,5

ผลลัพธ์

Given Tree: 4 2 5 1 3
Serialize: 1 2 3 4 5 N N N N N N
Deserialized Tree: 4 2 5 1 3