এই সমস্যায় একটি বাইনারি ট্রি দেওয়া আছে এবং আমাদের বাইনারি ট্রির সব ইন্টারনাল নোড প্রিন্ট করতে হবে।
বাইনারি ট্রি হলো একটি ট্রি যেখানে একটি নোডে সর্বোচ্চ ২টি চাইল্ড নোড থাকতে পারে। নোড বা ভার্টেক্সে কোনো চাইল্ড নাও থাকতে পারে, একটি চাইল্ড থাকতে পারে বা দুটি চাইল্ড থাকতে পারে।
ইন্টারনাল নোড হলো সেই নোড যেটির কমপক্ষে একটি চাইল্ড থাকে অর্থাৎ নন-লিফ নোডই ইন্টারনাল নোড।
উদাহরণ
আউটপুট - 7 4 9
এই সমস্যাটি সমাধানের জন্য বাইনারি ট্রি BFS (ব্রেডথ-ফার্স্ট সার্চ) ট্রাভার্সাল দিয়ে ট্রাভার্স করা হবে।
ট্রাভার্সালের সময় নোডগুলো একটি কিউতে পুশ করা হবে। কিউ থেকে এলিমেন্ট পপ করার সময় ট্রির যেসব নোডের চাইল্ড নেই সেগুলো ছাড়া বাকি নোডগুলো প্রিন্ট করা হবে।
বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right;
Node(int data) {
left = right = NULL;
this->data = data;
}
};
void printNonLeafNodes(Node* root) {
queue<Node*> treeNodes;
treeNodes.push(root);
while (!treeNodes.empty()) {
Node* curr = treeNodes.front();
treeNodes.pop();
bool isInternal = 0;
if (curr->left) {
isInternal = 1;
treeNodes.push(curr->left);
}
if (curr->right) {
isInternal = 1;
treeNodes.push(curr->right);
}
if (isInternal)
cout << curr->data << "\t";
}
}
int main() {
Node* root = new Node(43);
root->left = new Node(12);
root->right = new Node(78);
root->left->left = new Node(4);
root->right->left = new Node(9);
root->right->right = new Node(1);
root->right->right->right = new Node(50);
root->right->right->left = new Node(25);
cout << "All internal Nodes of the binary tree are :\n";
printNonLeafNodes(root);
return 0;
}
আউটপুট
All internal Nodes of the binary tree are : 43 12 78 1
