जैसा कि हम जानते हैं, एक कंप्लीट बाइनरी ट्री एक बाइनरी ट्री है जिसमें हर लेवल, संभवतः अंतिम को छोड़कर, पूरी तरह से भरा होता है, और सभी नोड्स जितना संभव हो उतना बाईं ओर होते हैं। हमें एक डेटा स्ट्रक्चर CBTInserter लिखना है जिसे एक कंप्लीट बाइनरी ट्री के साथ इनिशियलाइज़ किया जाता है और यह निम्नलिखित ऑपरेशन्स को सपोर्ट करता है -
- CBTInserter(TreeNode root) यह दिए गए ट्री पर डेटा स्ट्रक्चर को इनिशियलाइज़ करता है जिसका हेड नोड root है;
- CBTInserter.insert(int v) का उपयोग TreeNode को ट्री में इंसर्ट करने के लिए किया जाता है जिसका मान node.val = v होता है ताकि ट्री कंप्लीट रहे, और इंसर्ट किए गए TreeNode के पैरेंट का मान लौटाता है;
- CBTInserter.get_root() यह ट्री का हेड नोड लौटाता है।
उदाहरण के लिए, यदि हम ट्री को [1,2,3,4,5,6] के रूप में इनिशियलाइज़ करते हैं, फिर 7 और 8 इंसर्ट करते हैं, फिर ट्री पाने की कोशिश करते हैं, तो आउटपुट होगा: 3, 4,[1,2,3,4,5,6,7,8], 3 इसलिए क्योंकि 7 को 3 के नीचे इंसर्ट किया जाएगा, और 4 इसलिए क्योंकि 8 को 4 के नीचे इंसर्ट किया जाएगा।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
- एक क्यू q और एक रूट परिभाषित करें
- इनिशियलाइज़र दिए गए फुल बाइनरी ट्री को लेगा, फिर निम्नानुसार काम करेगा
- दिए गए रूट को रूट के रूप में सेट करें, रूट को q में डालें
- जब तक true -
- यदि रूट का लेफ्ट मौजूद है, तो रूट के लेफ्ट को q में डालें, अन्यथा लूप तोड़ें
- यदि रूट का राइट मौजूद है, तो रूट के राइट को q में डालें और q से फ्रंट नोड डिलीट करें, अन्यथा लूप तोड़ें
- इंसर्ट मेथड से, यह मान v लेगा
- पैरेंट := q का फ्रंट एलिमेंट सेट करें, टेम्प := मान v के साथ नया नोड, और इसे q में डालें
- यदि पैरेंट का लेफ्ट मौजूद नहीं है, तो पैरेंट का लेफ्ट := टेम्प सेट करें अन्यथा q से फ्रंट एलिमेंट डिलीट करें, और टेम्प को पैरेंट के राइट चाइल्ड के रूप में इंसर्ट करें
- पैरेंट का मान लौटाएं
- getRoot() मेथड से, रूट लौटाएं
उदाहरण (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 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 tree_level_trav(TreeNode*root){ if (root == NULL) return; cout << "["; queue<TreeNode *> q; TreeNode *curr; q.push(root); q.push(NULL); while (q.size() > 1) { curr = q.front(); q.pop(); if (curr == NULL){ q.push(NULL); } else { if(curr->left) q.push(curr->left); if(curr->right) q.push(curr->right); if(curr == NULL || curr->val == 0){ cout << "null" << ", "; } else { cout << curr->val << ", "; } } } cout << "]"<<endl; } class CBTInserter { public: queue <TreeNode*> q; TreeNode* root; CBTInserter(TreeNode* root) { this->root = root; q.push(root); while(1){ if(root->left){ q.push(root->left); } else break; if(root->right){ q.push(root->right); q.pop(); root = q.front(); } else break; } } int insert(int v) { TreeNode* parent = q.front(); TreeNode* temp = new TreeNode(v); q.push(temp); if(!parent->left){ parent->left = temp; } else { q.pop(); parent->right = temp; } return parent->val; } TreeNode* get_root() { return root; } }; main(){ vector<int> v = {1,2,3,4,5,6}; TreeNode *root = make_tree(v); CBTInserter ob(root); cout << (ob.insert(7)) << endl; cout << (ob.insert(8)) << endl; tree_level_trav(ob.get_root()); }इनपुट
ट्री को [1,2,3,4,5,6] के रूप में इनिशियलाइज़ करें, फिर ट्री में 7 और 8 इंसर्ट करें, फिर रूट ढूंढें
आउटपुट
3 4 [1, 2, 3, 4, 5, 6, 7, 8, ]
