इस समस्या में, हमें एक 2-D ऐरे दिया गया है जिसमें n-ary ट्री के एज होते हैं जहां एज n-ary ट्री के एज को परिभाषित करता है। हमें बने n-ary ट्री के सभी लीफ नोड्स प्रिंट करने हैं।
n-ary ट्री
n-ary ट्री एक ट्री है जिसमें अधिकतम n चाइल्ड होते हैं यानी एक नोड के 1, 2, ... n चाइल्ड नोड्स हो सकते हैं।
उदाहरण
Input: edge[][] = {{5,8}, {5,6}, {8,1}, {8,4}, {6,7}}
Output: 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
