আমাদের একটি বাইনারি ট্রি দেওয়া হয়েছে এবং কাজটি হল পুনরাবৃত্তিমূলক এবং পুনরাবৃত্তিমূলক পদ্ধতি ব্যবহার করে একটি বাইনারি গাছে উপলব্ধ পূর্ণ নোডের গণনা করা। পূর্ণ নোড হল সেই নোড যাদের সন্তান উভয়ই আছে এবং কোন সন্তান শূন্য নয়। মনে রাখবেন যে সম্পূর্ণ নোডগুলিতে আমরা ঠিক দুটি সন্তানের নোড বিবেচনা করি৷
বাইনারি ট্রি হল একটি বিশেষ ডেটা স্ট্রাকচার যা ডেটা স্টোরেজের উদ্দেশ্যে ব্যবহৃত হয়। একটি বাইনারি গাছের একটি বিশেষ শর্ত রয়েছে যে প্রতিটি নোডে সর্বাধিক দুটি শিশু থাকতে পারে। একটি বাইনারি ট্রিতে একটি অর্ডার করা অ্যারে এবং লিঙ্ক করা তালিকা উভয়ের সুবিধা রয়েছে কারণ অনুসন্ধানটি একটি সাজানো অ্যারের মতো দ্রুত এবং সন্নিবেশ বা মুছে ফেলার কাজটি লিঙ্ক করা তালিকার মতো দ্রুত। নন-লিফ নোডগুলি প্যারেন্ট নোড হিসাবেও পরিচিত কারণ তাদের 0-এর বেশি এবং দুটির কম সন্তান রয়েছে৷
বাইনারি গাছের গঠন নিচে দেওয়া হল -
উদাহরণস্বরূপ
ইনপুট −
আউটপুট − গণনা হল 2
ব্যাখ্যা − প্রদত্ত গাছে 2টি নোড আছে যেমন 10 এবং 20টি ঠিক দুটি সন্তান সহ বা পূর্ণ নোড অন্যান্য নোডের হয় একটি সন্তান আছে বা কোন সন্তান নেই৷
পুনরাবৃত্ত
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
একটি ডেটা অংশ, বাম পয়েন্টার এবং ডান পয়েন্টার সহ একটি নোডের একটি কাঠামো তৈরি করুন৷
-
একটি বাইনারি ট্রিতে নোড সন্নিবেশ করার জন্য একটি ফাংশন তৈরি করুন।
-
সম্পূর্ণ নোড গণনা করার জন্য একটি ফাংশন তৈরি করুন৷
-
একটি ফাংশনের ভিতরে, IF !node চেক করুন তারপরে একটি গাছে কোন নোড না থাকায় ফিরে যান৷
৷ -
সম্পূর্ণ নোডের গণনা সংরক্ষণ করতে একটি অস্থায়ী পরিবর্তনশীল গণনা ঘোষণা করুন
-
একটি কিউ টাইপ ভেরিয়েবল তৈরি করুন আসুন qu
বলি -
নোডগুলিকে qu.push(নোড)
হিসাবে একটি সারিতে পুশ করুন -
লুপ করার সময় !qu.empty()
-
একটি অস্থায়ী ভেরিয়েবল তৈরি করুন নোড টাইপের টেম্প বলুন এবং queue.front()
দিয়ে শুরু করুন -
qu.pop()
ব্যবহার করে উপাদানগুলি পপ করুন -
IF (!temp-> left AND temp-> right) চেক করুন তারপর গণনা 1 দ্বারা বৃদ্ধি করুন
-
IF (temp->left!=NULL) চেক করুন তারপর qu.push(temp->left)
-
IF (temp->right!=NULL) তারপর qu.push(temp->right)
চেক করুন -
গণনা ফেরত দিন
-
ফলাফল প্রিন্ট করুন।
উদাহরণ
// Iterative program to count full nodes
#include <iostream>
#include <queue>
using namespace std;
struct Node{
int data;
struct Node* left, *right;
};
// Function to count the full Nodes in a binary tree
int fullcount(struct Node* node){
// Check if tree is empty
if (!node){
return 0;
}
queue<Node *> myqueue;
// traverse using level order traversing
int result = 0;
myqueue.push(node);
while (!myqueue.empty()){
struct Node *temp = myqueue.front();
myqueue.pop();
if (temp->left && temp->right){
result++;
}
if (temp->left != NULL){
myqueue.push(temp->left);
}
if (temp->right != NULL){
myqueue.push(temp->right);
}
}
return result;
}
struct Node* newNode(int data){
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
int main(void){
struct Node *root = newNode(10);
root->left = newNode(20);
root->right = newNode(30);
root->left->left = newNode(40);
root->left->right = newNode(50);
root->left->left->right = newNode(60);
root->left->right->right = newNode(70);
cout <<"count is: "<<fullcount(root);
return 0;
} আউটপুট
আমরা উপরের কোডটি চালালে আমরা নিম্নলিখিত আউটপুট পাব −
count is: 2
পুনরাবৃত্ত
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
একটি ডেটা অংশ, বাম পয়েন্টার এবং ডান পয়েন্টার সহ একটি নোডের একটি কাঠামো তৈরি করুন৷
-
একটি বাইনারি ট্রিতে নোড সন্নিবেশ করার জন্য একটি ফাংশন তৈরি করুন।
-
সম্পূর্ণ নোড গণনা করার জন্য একটি ফাংশন তৈরি করুন৷
-
একটি ফাংশনের ভিতরে, IF !node চেক করুন তারপরে একটি গাছে কোন নোড না থাকায় ফিরে যান৷
৷ -
অর্ধেক নোডের গণনা সংরক্ষণ করতে একটি অস্থায়ী পরিবর্তনশীল গণনা ঘোষণা করুন
-
IF (root -> বাম এবং রুট->ডান) চেক করুন তারপর গণনা 1 দ্বারা বৃদ্ধি করুন
-
গণনা =গণনা + পুনরাবৃত্ত_কল_থেকে_এই_ফাংশন(রুট->বাম) +পুনরাবৃত্ত_ক্যাল_টু_এই_ফাংশন(রুট->ডান)
সেট করুন -
গণনা ফেরত দিন
-
ফলাফল প্রিন্ট করুন।
উদাহরণ
// Recursive program to count full nodes
#include <iostream>
using namespace std;
struct Node{
int data;
struct Node* left, *right;
};
// Function to get the count of full Nodes
int fullcount(struct Node* root){
if (root == NULL){
return 0;
}
int result = 0;
if (root->left && root->right){
result++;
}
result += (fullcount(root->left) +
fullcount(root->right));
return result;
}
struct Node* newNode(int data){
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
int main(){
struct Node *root = newNode(10);
root->left = newNode(20);
root->right = newNode(30);
root->left->left = newNode(40);
root->left->right = newNode(50);
root->left->left->right = newNode(60);
root->left->right->right = newNode(70);
cout <<"count is: "<<fullcount(root);
return 0;
} আউটপুট
আমরা উপরের কোডটি চালালে আমরা নিম্নলিখিত আউটপুট পাব −
count is: 2
