समस्या विवरण
मान लीजिए हमारे पास एक बाइनरी ट्री है। जैसा कि हम जानते हैं, बाइनरी ट्री का संक्षिप्त एन्कोडिंग न्यूनतम संभव स्थान के करीब प्रदर्शन करता है। 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(root, struc, data) परिभाषित करें:
- यदि root NULL है, तो struc में 0 डालें और वापस लौटें
- struc में 1 डालें
- root के मान को data में डालें
- Encode(left, struc, data)
- Encode(right, struc, data)
- फ़ंक्शन Decode(struc, data) परिभाषित करें:
- यदि struc का आकार <= 0, तो NULL वापस करें
- b := struc का पहला तत्व
- struc से पहला तत्व हटाएं
- यदि b == 1:
- key := data का पहला तत्व
- data से पहला तत्व हटाएं
- key के साथ नया नोड बनाएं
- left := Decode(struc, data)
- right := 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);
}
}
int 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";
for(auto si = struc.begin(); si != struc.end(); ++si)
cout << *si << " ";
cout << "\nData List\n";
for(auto 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