Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

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


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

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

तो, यदि इनपुट इस तरह है


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

तो आउटपुट होगा Serialize − 1 2 3 4 5 N N N N N N Deserialized Tree: 4 2 5 1 3।

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

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

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

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

  • root को q में डालें

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

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

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

    • यदि curr उपलब्ध नहीं है, तो −

      • ret := ret को "N" के साथ जोड़ें

      • ret := ret को खाली स्थान के साथ जोड़ें

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

    • ret := ret + curr का मान

    • ret := ret + खाली स्थान

    • curr का left q के अंत में

    • curr का right q के अंत में

  • ret लौटाएं

  • deserialize() नामक एक फ़ंक्शन परिभाषित करें, जो data लेगा,

  • यदि data[0] 'N' के समान है, तो −

    • NULL लौटाएं

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

  • एक ऐरे v परिभाषित करें

  • i := 0 से आरंभ करें, जब i − data का आकार, अद्यतन करें (i को 1 से बढ़ाएं), करें −

    • यदि data[i] खाली स्थान के समान है, तो −

      • temp को v के अंत में डालें

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

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

    • temp := temp + data[i]

  • newRoot = v[0] के साथ नया नोड

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

  • newRoot को q में डालें

  • i := 1

  • जब तक (q खाली नहीं है और i, v के आकार से कम), करें −

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

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

    • यदि v[i] "N" के बराबर नहीं है, तो −

      • parent का left := v[i] के साथ नया नोड

      • parent के left को q में डालें

    • (i को 1 से बढ़ाएं)

    • यदि v[i] "N" के बराबर नहीं है, तो −

      • parent का right := v[i] के साथ नया नोड

      • parent के right को q में डालें

    • (i को 1 से बढ़ाएं)

  • newRoot लौटाएं

उदाहरण 

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −

#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

  1. C++ में बाइनरी ट्री प्रूनिंग C++ में बाइनरी ट्री प्रूनिंग

    मान लीजिए हमारे पास एक बाइनरी ट्री का हेड नोड root है, जहाँ प्रत्येक नोड का मान या तो 0 या 1 है। हमें वही ट्री लौटाना है जहाँ हर वह सबट्री हटा दी गई हो जिसमें 1 नहीं है। उदाहरण: इनपुट ट्री [1,1,0,1,1,0,1,0] के लिए, आउटपुट ट्री में केवल वही नोड्स रहेंगे जिनके सबट्री में कम से कम एक 1 है। पोस्ट-ऑर्

  1. C++ में अधिकतम बाइनरी ट्री निर्माण C++ में अधिकतम बाइनरी ट्री निर्माण

    मान लीजिए हमारे पास एक पूर्णांक सरणी है जिसके सभी तत्व अद्वितीय हैं। एक अधिकतम बाइनरी ट्री निम्न नियमों से बनता है: रूट सरणी का अधिकतम तत्व होता है। बायाँ सबट्री अधिकतम तत्व के बाएँ भाग से बने सबसरणी का अधिकतम ट्री होता है। दायाँ सबट्री अधिकतम तत्व के दाएँ भाग से बने सबसरणी का अधिकतम ट्री होता है।

  1. C++ में बाइनरी ट्री को बाइनरी सर्च ट्री में रूपांतरण C++ में बाइनरी ट्री को बाइनरी सर्च ट्री में रूपांतरण

    एक बाइनरी ट्री एक विशेष प्रकार का ट्री है जिसमें ट्री का प्रत्येक नोड अधिकतम दो चाइल्ड नोड रख सकता है। इन चाइल्ड नोड्स को राइट चाइल्ड और लेफ्ट चाइल्ड के नाम से जाना जाता है। एक साधारण बाइनरी ट्री है - बाइनरी सर्च ट्री (BST) एक विशेष प्रकार का ट्री है जो निम्नलिखित नियमों का पालन करता है - बाएं चाइ