এই সমস্যায় একটি ২-D অ্যারে দেওয়া আছে যেটিতে n-এরি ট্রির এজ (edge) সংরক্ষিত আছে। আমাদের তৈরি n-এরি ট্রির সব লিফ নোড প্রিন্ট করতে হবে।
n-এরি ট্রি হলো এমন ট্রি যেটির সর্বোচ্চ n সংখ্যক চাইল্ড থাকে অর্থাৎ একটি নোডে ১, ২, ... n চাইল্ড নোড থাকতে পারে।
উদাহরণ
ইনপুট: edge[][] = {{5,8}, {5,6}, {8,1}, {8,4}, {6,7}}
আউটপুট: 1 4 7
ব্যাখ্যা - এজ অ্যারে ব্যবহার করে ট্রি তৈরি করা যাক -
এই ট্রির লিফ নোডগুলো: 1, 4, 7।
এই সমস্যাটি সমাধানের জন্য ট্রি DFS (ডেপথ-ফার্স্ট সার্চ) দিয়ে ট্রাভার্স করা হবে (এটি প্রতিটি সাবট্রির লিফ নোড খুঁজে বের করবে)। ভিজিটেড নোডগুলো মার্ক করা হবে। যদি নোডের চাইল্ড থাকে (লিফ নোড না হয়), তবে ফ্ল্যাগ সেট করা হবে এবং যেসব নোডের চাইল্ড নেই সেগুলো প্রিন্ট করা হবে।
বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
void DFS(list<int> t[], int node, int parent) {
int flag = 0;
for (auto ir : t[node]) {
if (ir != parent) {
flag = 1;
DFS(t, ir, node);
}
}
if (flag == 0)
cout << node << "\t";
}
int main() {
list<int> t[1005];
pair<int, int> edges[] = {
{ 1, 2 },
{ 1, 3 },
{ 2, 4 },
{ 3, 5 },
{ 3, 6 },
{ 3, 7 },
{ 6, 8 }
};
int cnt = sizeof(edges) / sizeof(edges[0]);
int node = cnt + 1;
for (int i = 0; i < cnt; i++) {
t[edges[i].first].push_back(edges[i].second);
t[edges[i].second].push_back(edges[i].first);
}
cout << "Leaf nodes of the tree are:\n";
DFS(t, 1, 0);
return 0;
}
আউটপুট
Leaf nodes of the tree are : 4 5 8 7
