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 খালি না:
    • curr = q.front(); q.pop()
    • যদি curr নাল: ret += "N "; continue
    • ret += to_string(curr->val) + " "
    • curr->left এবং curr->right q-তে পুশ
  • ret ফেরত
• deserialize(data) ফাংশন:
  • যদি data[0] == 'N': NULL ফেরত
  • temp := খালি স্ট্রিং, ভেক্টর v
  • i = 0 থেকে data.size()-1:
    • যদি data[i] == ' ': v.push_back(temp); temp = ""; continue
    • temp += data[i]
  • newRoot = new TreeNode(stoi(v[0]))
  • একটি কিউ q, newRoot পুশ
  • i := 1
  • যখন q খালি না এবং i < v.size():
    • parent = q.front(); q.pop()
    • যদি v[i] != "N": parent->left = new TreeNode(stoi(v[i])); q.push(parent->left)
    • i++
    • যদি v[i] != "N": parent->right = new TreeNode(stoi(v[i])); q.push(parent->right)
    • i++
  • 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 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 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 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 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 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;
    }
};

int main() {
    Codec ob;
    vector 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