আমাদের একটি বাইনারি ট্রি দেওয়া হয়েছে এবং কাজটি হল পুনরাবৃত্তিমূলক এবং পুনরাবৃত্তিমূলক পদ্ধতি ব্যবহার করে একটি বাইনারি গাছে উপলব্ধ অর্ধেক নোডের গণনা করা। হাফ নোড হল সেই নোড যাদের একটি মাত্র সন্তান আছে এবং অন্য একটি শিশু শূন্য। মনে রাখবেন যে অর্ধেক নোডগুলিতে আমরা লিফ নোডগুলি বিবেচনা করি না৷
বাইনারি ট্রি হল একটি বিশেষ ডেটা স্ট্রাকচার যা ডেটা স্টোরেজের উদ্দেশ্যে ব্যবহৃত হয়। একটি বাইনারি গাছের বিশেষ শর্ত থাকে যে প্রতিটি নোডে সর্বাধিক দুটি শিশু থাকতে পারে। একটি বাইনারি ট্রিতে একটি অর্ডার করা অ্যারে এবং লিঙ্ক করা তালিকা উভয়ের সুবিধা রয়েছে কারণ অনুসন্ধানটি একটি সাজানো অ্যারের মতো দ্রুত এবং সন্নিবেশ বা মুছে ফেলার কাজটি লিঙ্ক করা তালিকার মতো দ্রুত। নন-লিফ নোডগুলি প্যারেন্ট নোড হিসাবেও পরিচিত কারণ তাদের 0-এর বেশি এবং দুটির কম সন্তান রয়েছে৷
বাইনারি গাছের গঠন নিচে দেওয়া হল -
উদাহরণস্বরূপ
ইনপুট −
আউটপুট − গণনা হল 2
ব্যাখ্যা − প্রদত্ত গাছে 2টি নোড রয়েছে যেমন 40 এবং 50টি ঠিক একটি চাইল্ড বা অর্ধেক নোড সহ অন্যান্য নোডের দুটি বাচ্চা থাকতে পারে বা কোন সন্তান নেই৷
পুনরাবৃত্ত
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
একটি ডেটা অংশ, বাম পয়েন্টার এবং ডান পয়েন্টার সহ একটি নোডের একটি কাঠামো তৈরি করুন৷
-
একটি বাইনারি ট্রিতে নোড সন্নিবেশ করার জন্য একটি ফাংশন তৈরি করুন।
-
অর্ধেক নোড গণনা করার জন্য একটি ফাংশন তৈরি করুন।
-
একটি ফাংশনের ভিতরে, IF !node চেক করুন তারপরে একটি গাছে কোন নোড না থাকায় ফিরে যান৷
৷ -
অর্ধেক নোডের গণনা সংরক্ষণ করতে একটি অস্থায়ী পরিবর্তনশীল গণনা ঘোষণা করুন
-
একটি কিউ টাইপ ভেরিয়েবল তৈরি করুন আসুন qu
বলি -
নোডগুলিকে qu.push(নোড)
হিসাবে একটি সারিতে পুশ করুন -
লুপ করার সময় !qu.empty()
-
একটি অস্থায়ী ভেরিয়েবল তৈরি করুন নোড টাইপের টেম্প বলুন এবং queue.front()
দিয়ে শুরু করুন -
qu.pop()
ব্যবহার করে উপাদানগুলি পপ করুন -
IF (!temp-> leftAND temp-> right) বা (temp->left AND !temp->right) চেক করুন তারপর গণনা 1 দ্বারা বৃদ্ধি করুন
-
IF (temp->left!=NULL) চেক করুন তারপর qu.push(temp->left)
-
গণনা ফেরত দিন
-
ফলাফল প্রিন্ট করুন।
উদাহরণ
// Program to count half nodes in a Binary Tree
#include <iostream>
#include <queue>
using namespace std;
struct Node{
int data;
struct Node* left, *right;
};
// Function to get the count of half Nodes
int halfcount(struct Node* node){
// If tree is empty
if (!node)
return 0;
int result = 0; // Initialize count of half nodes
// Do level order traversal starting from root
queue<Node *> myqueue;
myqueue.push(node);
while (!myqueue.empty()){
struct Node *temp = myqueue.front();
myqueue.pop();
if ((!temp->left && temp->right) || (temp->left && !temp->right)){
result++;
}
if (temp->left != NULL){
myqueue.push(temp->left);
}
if (temp->right != NULL){
myqueue.push(temp->right);
}
}
return result;
}
/* To allocate new Node with the given data and NULL left
and right pointers. */
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: "<<halfcount(root);
return 0;
} আউটপুট
আমরা উপরের কোডটি চালালে আমরা নিম্নলিখিত আউটপুট পাব -
count is: 2
পুনরাবৃত্ত
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
একটি ডেটা অংশ, বাম পয়েন্টার এবং ডান পয়েন্টার সহ একটি নোডের একটি কাঠামো তৈরি করুন৷
-
একটি বাইনারি ট্রিতে নোড সন্নিবেশ করার জন্য একটি ফাংশন তৈরি করুন।
-
অর্ধেক নোড গণনা করার জন্য একটি ফাংশন তৈরি করুন।
-
একটি ফাংশনের ভিতরে, IF !node চেক করুন তারপরে একটি গাছে কোন নোড না থাকায় ফিরে যান৷
৷ -
অর্ধেক নোডের গণনা সংরক্ষণ করতে একটি অস্থায়ী পরিবর্তনশীল গণনা ঘোষণা করুন
-
চেক করুন যদি (root -> left =NULL AND root->right !=NULL) OR (root -> left !=NULL AND root->right ==NULL) তারপর গণনা 1 দ্বারা বৃদ্ধি করুন
-
গণনা =গণনা + পুনরাবৃত্ত_কল_থেকে_এই_ফাংশন(রুট->বাম) +পুনরাবৃত্ত_ক্যাল_টু_এই_ফাংশন(রুট->ডান)
সেট করুন -
গণনা ফেরত দিন
-
ফলাফল প্রিন্ট করুন।
উদাহরণ
// Recursive program to count half nodes
#include <bits/stdc++.h>
using namespace std;
// A binary tree Node has data, pointer to left
// child and a pointer to right child
struct Node{
int data;
struct Node* left, *right;
};
int halfcount(struct Node* root){
if (root == NULL)
return 0;
int result = 0;
if ((root->left == NULL && root->right != NULL) || (root->left != NULL && root->right ==
NULL)){
result++;
}
result += (halfcount(root->left) + halfcount(root->right));
return result;
}
/* to allocate a new Node with the given data and NULL left
and right pointers. */
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: "<<halfcount(root);
return 0;
} আউটপুট
আমরা উপরের কোডটি চালালে আমরা নিম্নলিখিত আউটপুট পাব -
count is: 2
