মান লিইয়ে নিই আমাদের কাছে একটি বাইনারি ট্রি রয়েছে। যেনে আমরা জানি বাইনারি ট্রির সংক্ষিপ্ত এনকোডিং সম্ভাব্য ন্যূনতম স্পেসের খুব কাছাকাছি। n-তম ক্যাটালান সংখ্যা nটি ভিন্ন নোডের সাথে গঠনগতভাবে ভিন্ন বাইনারি ট্রি সংখ্যাকে নির্দেশ করে। যদি n বড় হয়, তবে এটি প্রায় 4^n; সুতরাং, এনকোড করার জন্য ন্যূনতম log2(4^n) = 2n বিট প্রয়োজন। একটি সংক্ষিপ্ত বাইনারি ট্রি তাই 2n + O(n) বিট খরচ করে।
সুতরাং, যদি ইনপুট এমন হয়:
তব আউটপুট হবে:
এনকোডেড -
স্ট্রাকচার লিস্ট 1 1 1 0 0 1 0 0 1 0 1 0 0
ডেটা লিস্ট 10 20 40 50 30 70
ডিকোডেড - উপরে দেখানো ট্রি।
সমাধান পদ্ধতি
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
- Encode() ফাংশন সংজ্ঞায়িত করুন, যা রুট, struc নামক একটি লিস্ট, data নামক একটি লিস্ট গ্রহণ করবে,
- যদি রুট NULL-এর সমান হয়, তবে:
- struc-এর শেষে 0 যোগ করুন
- ফেরত দিন
- struc-এর শেষে 1 যোগ করুন
- data-এর শেষে রুটের মান যোগ করুন
- Encode(রুটের বাম, struc, data)
- Encode(রুটের ডান, struc, data)
- Decode() ফাংশন সংজ্ঞায়িত করুন, যা struc নামক একটি লিস্ট, data নামক একটি লিস্ট গ্রহণ করবে,
- যদি struc-এর আকার <= 0, তবে:
- NULL ফেরত দিন
- b := struc-এর প্রথম উপাদান
- struc-এর সামনের উপাদানটি মুছুন
- যদি b, 1-এর সমান হয়, তবে:
- key := data-এর প্রথম উপাদান
- data-এর সামনের উপাদানটি মুছুন
- root = key দিয়ে নতুন নোড
- রুটের বাম := Decode(struc, data)
- রুটের ডান := Decode(struc, data)
- root ফেরত দিন
- NULL ফেরত দিন
উদাহরণ (C++)
বेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#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 Encode(TreeNode *root, list<bool>&struc, list<int>&data){ if(root == NULL){ struc.push_back(0); return; } struc.push_back(1); data.push_back(root->val); Encode(root->left, struc, data); Encode(root->right, struc, data); } TreeNode *Decode(list<bool>&struc, list<int>&data){ if(struc.size() <= 0) return NULL; bool b = struc.front(); struc.pop_front(); if(b == 1){ int key = data.front(); data.pop_front(); TreeNode *root = new TreeNode(key); root->left = Decode(struc, data); root->right = Decode(struc, data); return root; } return NULL; } void preorder_trav(TreeNode* root){ if(root){ cout << "key: "<< root->val; if(root->left) cout << " | left child: "<< root->left->val; if(root->right) cout << " | right child: "<< root->right->val; cout << endl; preorder_trav(root->left); preorder_trav(root->right); } } main() { TreeNode *root = new TreeNode(10); root->left = new TreeNode(20); root->right = new TreeNode(30); root->left->left = new TreeNode(40); root->left->right = new TreeNode(50); root->right->right = new TreeNode(70); cout << "The Tree\n"; preorder_trav(root); list<bool> struc; list<int> data; Encode(root, struc, data); cout << "\nEncoded Tree\n"; cout << "Structure List\n"; list<bool>::iterator si; // Structure iterator for(si = struc.begin(); si != struc.end(); ++si) cout << *si << " "; cout << "\nData List\n"; list<int>::iterator di; // Data iIterator for(di = data.begin(); di != data.end(); ++di) cout << *di << " "; TreeNode *newroot = Decode(struc, data); cout << "\n\nPreorder traversal of decoded tree\n"; preorder_trav(newroot); }
इनपुट
root->left = new TreeNode(20); root->right = new TreeNode(30); root->left->left = new TreeNode(40); root->left->right = new TreeNode(50); root->right->right = new TreeNode(70);
आउटपुट
The Tree key: 10 | left child: 20 | right child: 30 key: 20 | left child: 40 | right child: 50 key: 40 key: 50 key: 30 | right child: 70 key: 70 Encoded Tree Structure List 1 1 1 0 0 1 0 0 1 0 1 0 0 Data List 10 20 40 50 30 70 Preorder traversal of decoded tree key: 10 | left child: 20 | right child: 30 key: 20 | left child: 40 | right child: 50 key: 40 key: 50 key: 30 | right child: 70 key: 70
