আমাদের একটি বাইনারি গাছ দেওয়া হয়েছে এবং কাজটি হল একটি বাইনারি গাছে উপলব্ধ নন-লিফ নোডের গণনা করা।
বাইনারি ট্রি হল একটি বিশেষ ডেটা স্ট্রাকচার যা ডেটা স্টোরেজের উদ্দেশ্যে ব্যবহৃত হয়। একটি বাইনারি গাছের একটি বিশেষ শর্ত রয়েছে যে প্রতিটি নোডে সর্বাধিক দুটি শিশু থাকতে পারে। একটি বাইনারি ট্রিতে একটি অর্ডার করা অ্যারে এবং লিঙ্ক করা তালিকা উভয়ের সুবিধা রয়েছে কারণ অনুসন্ধানটি একটি সাজানো অ্যারের মতো দ্রুত এবং সন্নিবেশ বা মুছে ফেলার কাজটি লিঙ্ক করা তালিকার মতো দ্রুত। নন-লিফ নোডগুলি প্যারেন্ট নোড হিসাবেও পরিচিত কারণ তাদের 0-এর বেশি এবং দুটির কম সন্তান রয়েছে৷
বাইনারি গাছের গঠন নিচে দেওয়া হল -
উদাহরণস্বরূপ
ইনপুট −
আউটপুট − নন-লিফ নোডের সংখ্যা হল:3
ব্যাখ্যা − প্রদত্ত গাছে, আমাদের 27, 14 এবং 35টি নন-লিফ নোড হিসাবে রয়েছে কারণ তাদের 0-এর বেশি এবং 2-এর কম বাচ্চা রয়েছে৷
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
একটি বাইনারি ট্রির গঠন তৈরি করুন যাতে একটি বাম নোডে পয়েন্টার, একটি ডান নোডে পয়েন্টার এবং একটি নোডে সংরক্ষিত একটি ডেটা অংশ
-
একটি ফাংশন তৈরি করুন যা একটি নোড সন্নিবেশ করবে যখনই এই ফাংশনটি কল করা হবে। এর জন্য, একটি নতুন নোডে ডেটা সন্নিবেশ করান এবং একটি নতুন নোডের ডান এবং বাম পয়েন্টারকে একটি NULL এ সেট করুন এবং নোডটি ফেরত দিন৷
-
একটি পুনরাবৃত্ত ফাংশন তৈরি করুন যা একটি বাইনারি গাছে নন-লিফ নোডের সংখ্যা গণনা করবে৷
- চেক করুন রুট যদি NULL হয় বা রুটের বাম হয় NULL এবং রুটের ডানদিকে NULL হয় তাহলে 0 ফেরত দিন
- লেম পয়েন্টার সহ এই ফাংশনে 1 + রিকারসিভ কল রিটার্ন করুন + ডান পয়েন্টার সহ এই ফাংশনে রিকারসিভ কল করুন
-
গণনা প্রিন্ট করুন
উদাহরণ
#include <iostream>
using namespace std;
// Node's structure
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// To define the new node
struct Node* newNode(int data){
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
// Count the non leaf nodes.
int nonleaf(struct Node* root){
if (root == NULL || (root->left == NULL && root->right == NULL)){
return 0;
}
return 1 + nonleaf(root->left) + nonleaf(root->right);
}
// Main function
int main(){
struct Node* root = newNode(10);
root->left = newNode(21);
root->right = newNode(33);
root->left->left = newNode(48);
root->left->right = newNode(51);
cout << nonleaf(root);
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −
উৎপন্ন করবেcount of non-leaf nodes is: 2
