सी ++ में बाइनरी ट्री को सीरियलाइज़ और डिसेरिएलाइज़ करें

मान लीजिए कि हमारे पास एक बाइनरी ट्री है और हमें उन्हें क्रमबद्ध और डिसेरिएलाइज़ करना है। जैसा कि हम जानते हैं कि क्रमांकन डेटा संरचना या ऑब्जेक्ट को बिट्स के अनुक्रम में परिवर्तित करने की प्रक्रिया है, इसलिए हम उन्हें एक फ़ाइल या मेमोरी बफर में स्टोर कर सकते हैं, और जिसे बाद में उसी या किसी अन्य कंप्यूटर वातावरण में फिर से बनाया जा सकता है।

यहां हमें बाइनरी ट्री को क्रमबद्ध और अक्रमांकन करने के लिए एक एल्गोरिथ्म तैयार करना होगा। बाइनरी ट्री एक जड़ वाला पेड़ है जिसमें प्रत्येक नोड में 2 से अधिक बच्चे नहीं होते हैं।

तो, अगर इनपुट पसंद है

तो आउटपुट सीरियलाइज होगा - 1 2 3 4 5 एन एन एन एन एन एन डीसेरियलाइज्ड ट्री:4 2 5 1 3.

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फ़ंक्शन को परिभाषित करें serialize(), यह जड़ लेगा,

• रिट:=खाली स्ट्रिंग

• एक कतार को परिभाषित करें q

• q में रूट डालें

• जबकि (नहीं q खाली है), करें -

  • curr =q का पहला तत्व

  • q से तत्व हटाएं

  • अगर कर्व उपलब्ध नहीं है, तो -

    • ret :=ret concatenate "N"

    • ret :=ret concatenate रिक्त स्थान

    • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

  • रिट:=रेट + कर्व का मूल्य

  • रिट :=रिट + रिक्त स्थान

  • q के अंत में curr के बाएँ

  • q के अंत में curr का अधिकार

• वापसी रिट

• एक फ़ंक्शन को परिभाषित करें deserialize(), यह डेटा लेगा,

• अगर डेटा [0] 'एन' के समान है, तो -

  • वापसी शून्य

• अस्थायी:=खाली स्ट्रिंग

• सरणी को परिभाषित करें v

• इनिशियलाइज़ i :=0 के लिए, जब i - डेटा का आकार, अपडेट (i से 1 की वृद्धि), करें -

  • यदि डेटा [i] रिक्त स्थान के समान है, तो -

    • v के अंत में अस्थायी डालें

    • अस्थायी:=रिक्त स्ट्रिंग

    • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

  • अस्थायी:=अस्थायी + डेटा [i]

• newRoot =नया नोड v[0]

  . के साथ

• एक कतार को परिभाषित करें q

• q में newRoot डालें

• मैं :=1

• जबकि (नहीं q खाली है और i

  • पैरेंट =q का पहला तत्व

  • q से तत्व हटाएं

  • अगर v[i] "N" के बराबर नहीं है, तो -

    • माता-पिता के बाईं ओर:=नया नोड v[i]

      . के साथ

    • माता-पिता के बाईं ओर q में डालें

  • (मैं 1 से बढ़ाइए)

  • अगर v[i] "N" के बराबर नहीं है, तो -

    • माता-पिता का अधिकार:=नया नोड v[i]

      . के साथ

    • माता-पिता के अधिकार को q में डालें

  • (मैं 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