जैसा कि हम जानते हैं कि एक पूर्ण बाइनरी ट्री एक बाइनरी ट्री होता है जिसमें संभवतः अंतिम को छोड़कर प्रत्येक स्तर पूरी तरह से भरा होता है, और सभी नोड्स यथासंभव दूर छोड़े जाते हैं। हमें एक डेटा संरचना CBTInserter लिखनी है जो एक पूर्ण बाइनरी ट्री के साथ आरंभ की गई है और यह निम्नलिखित कार्यों का समर्थन करती है-
-
CBTInserter(TreeNode root) यह किसी दिए गए ट्री पर हेड नोड रूट के साथ डेटा संरचना को इनिशियलाइज़ करता है;
-
CBTInserter.insert(int v) एक ट्रीनोड को ट्री में एक मान नोड.वैल =v के साथ सम्मिलित करने के लिए उपयोग किया जाएगा ताकि ट्री पूर्ण रहे, और सम्मिलित ट्रीनोड के पैरेंट का मान लौटाए;
-
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 में डालें
-
जबकि सच -
-
यदि रूट का बायां हिस्सा मौजूद है, तो रूट के बाईं ओर 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());
} इनपुट
Initialize the tree as [1,2,3,4,5,6], then insert 7 and 8 into the tree, then find root
आउटपुट
3 4 [1, 2, 3, 4, 5, 6, 7, 8, ]