इस समस्या में, हमें एक 2-डी सरणी दी जाती है जिसमें एक 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. हैं