এই সমস্যায় একটি বাইনারি ট্রি দেওয়া আছে। আমাদের ট্রির যেসব নোড ফুল নোড সেগুলো প্রিন্ট করতে হবে।
বাইনারি ট্রি হলো একটি ট্রি যেখানে একটি নোডে সর্বোচ্চ ২টি চাইল্ড নোড থাকতে পারে। নোড বা ভার্টেক্সে কোনো চাইল্ড নাও থাকতে পারে, একটি চাইল্ড থাকতে পারে বা দুটি চাইল্ড থাকতে পারে।
ফুল নোড হলো সেই নোড যেটির বাম ও ডান উভয় চাইল্ড উপলব্ধ থাকে। অর্থাৎ বাম ও ডান চাইল্ড বিশিষ্ট নোডকে ফুল নোড বলা হয়। উপরের বাইনারি ট্রিতে ৪ এবং ৯ ফুল নোড।
উদাহরণ
আউটপুট - 4 9
এই সমস্যাটি সমাধানের একটি সহজ পদ্ধতি হলো ট্রি ট্রাভার্স করা যেকোনো ট্রাভার্সাল অ্যালগরিদম দিয়ে। বর্তমান নোডে বাম ও ডান চাইল্ড আছে কিনা চেক করা হবে। যদি হয় তবে নোডের মান প্রিন্ট করা হবে অন্যথায় ছেড়ে দেওয়া হবে।
বাস্তবায়ন
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
Node *insertNode(int data) {
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void printFullNode(Node *root) {
if (root != NULL) {
printFullNode(root->left);
if (root->left != NULL && root->right != NULL)
cout << root->data << "\t";
printFullNode(root->right);
}
}
int main() {
Node* root = insertNode(100);
root->left = insertNode(56);
root->right = insertNode(12);
root->left->left = insertNode(89);
root->right->left = insertNode(32);
root->right->right = insertNode(45);
cout << "All full nodes of the tree are :\n";
printFullNode(root);
return 0;
}
আউটপুট
All full nodes of the tree are : 100 12
