আমাদের একটি বাইনারি ট্রি দেওয়া আছে এবং আমাদের কাজ হল বাইনারি ট্রিতে থাকা নন-লিফ নোডগুলির সংখ্যা গণনা করা।
বাইনারি ট্রি হল ডেটা সংরক্ষণের জন্য একটি বিশেষ ডেটা কাঠামো। একটি বাইনারি ট্রির বিশেষ শর্ত হল প্রতিটি নোডের সর্বোচ্চ দুটি চাইল্ড হতে পারে। বাইনারি ট্রিতে সর্টেড অ্যারে এবং লিঙ্কড লিস্ট উভয়ের সুবিধা থাকে কারণ সার্চিং সর্টেড অ্যারের মতো দ্রুত এবং ইনসারশন/ডিলিশন লিঙ্কড লিস্টের মতো দ্রুত। নন-লিফ নোডকে পেরেন্ট নোডও বলা হয় কারণ তাদের 0-এর বেশি এবং 2-এর কম চাইল্ড থাকে।
বাইনারি ট্রির কাঠামো নিচে দেওয়া হল −
উদাহরণ
ইনপুট −
আউটপুট − নন-লিফ নোডের গণনা: 3
ব্যাখ্যা − দেওয়া ট্রিতে 27, 14 এবং 35 নন-লিফ নোড কারণ তাদের 0-এর বেশি এবং 2-এর কম চাইল্ড রয়েছে।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
- বাইনারি ট্রির কাঠামো তৈরি করুন যাতে থাকে: বাম নোডের পয়েন্টার, ডান নোডের পয়েন্টার এবং নোডে সংরক্ষিত ডেটা
- একটি ফাংশন তৈরি করুন যা কল করা হলে একটি নোড ইনসার্ট করবে। তার জন্য নতুন নোডে ডেটা ইনসার্ট করুন এবং নতুন নোডের ডান ও বাম পয়েন্টার NULL সেট করুন এবং নোডটি ফেরত দিন
- একটি রিকারসিভ ফাংশন তৈরি করুন যা বাইনারি ট্রিতে নন-লিফ নোডের সংখ্যা গণনা করবে।
- যদি রুট NULL হয় অথবা রুটের বাম NULL এবং ডান NULL হয় তবে 0 ফেরত দিন
- 1 + বাম পয়েন্টারের সাথে রিকারসিভ কল + ডান পয়েন্টারের সাথে রিকারসিভ কল ফেরত দিন
- গণনা প্রিন্ট করুন
উদাহরণ কোড
#include <iostream>
using namespace std;
// নোডের কাঠামো
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// নতুন নোড সংজ্ঞায়িত করুন
struct Node* newNode(int data) {
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
// নন-লিফ নোড গণনা
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 ফাংশন
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
