যে কারণে কমপ্লিট বাইনারি ট্রি হলো একটি বাইনারি ট্রি যেখানে প্রতিটি লেভেল, সম্ভবত লাস্ট লেভেল বাদে, পুরোপুরি ফিল্ড থাকে, এবং সব নোড যতটা সম্ভব বাম দিকে থাকে। আমাদের `CBTInserter` নামক একটি ডেটা স্ট্রাকচার লিখতে হবে যা একটি কমপ্লিট বাইনারি ট্রি দিয়ে ইনিশিয়ালাইজ হবে এবং নিচের অপারেশনগুলো সাপোর্ট করবে -
- `CBTInserter(TreeNode root)` এটি দিয়ে দেয়া ট্রি রুট নোড `root` দিয়ে ডেটা স্ট্রাকচার ইনিশিয়ালাইজ করবে;
- `CBTInserter.insert(int v)` একটি TreeNode ইনসার্ট করবে ট্রিতে `node.val = v` মান দিয়ে যাতে ট্রি কমপ্লিট থাকে, এবং ইনসার্ট করা TreeNode-এর পেরেন্টের মান রিটার্ন করবে;
- `CBTInserter.get_root()` ট্রির হেড নোড রিটার্ন করবে।
উদাহরণস্বরূপ, যদি আমরা ট্রি `[1,2,3,4,5,6]` দিয়ে ইনিশিয়ালাইজ করি, তারপর ৭ এবং ৮ ইনসার্ট করি, তারপর ট্রি পেতে চাই, তবে আউটপুট হবে: 3, 4, [1,2,3,4,5,6,7,8], ৩ হলো কারণ ৭, ৩-এর নিচে ইনসার্ট হবে, এবং ৪ হলো কারণ ৮, ৪-এর নিচে ইনসার্ট হবে।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব -
- একটি কিউ `q`, এবং একটি `root` সংজ্ঞায়িত করুন
- ইনিশিয়ালাইজার পুরো বাইনারি ট্রি নেবে, তারপর নিচের মোতাবিক কাজ করবে
- `root`-কে দেওয়া `root` সেট করুন, `root`-কে `q`-তে ইনসার্ট করুন
- যখন `true` -
- যদি `root`-এর বাম থাকে, তবে `root`-এর বাম `q`-তে ইনসার্ট করুন, অন্যথায় ব্রেক করুন
- যদি `root`-এর ডান থাকে, তবে `root`-এর ডান `q`-তে ইনসার্ট করুন এবং `q`-এর ফ্রন্ট নোড ডিলিট করুন, অন্যথায় ব্রেক করুন
- `insert` মেথড থেকে, এটি ভ্যালু `v` নেবে
- `parent := q`-এর ফ্রন্ট এলিমেন্ট, `temp :=` ভ্যালু `v` দিয়ে নতুন নোড, এবং `q`-তে ইনসার্ট করুন
- যদি `parent`-এর বাম না থাকে, তবে `parent`-এর বাম := `temp` সেট করুন অন্যথায় `q`-এর ফ্রন্ট এলিমেন্ট ডিলিট করুন, এবং `temp`-কে `parent`-এর ডান চাইল্ড হিসেবে ইনসার্ট করুন
- `parent`-এর মান রিটার্ন করুন
- `getRoot()` মেথড থেকে, `root` রিটার্ন করুন
উদাহরণ (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, ]
