इस ट्यूटोरियल में, हम एक प्रोग्राम लिखने जा रहे हैं जो n-ary ट्री में प्रत्येक नोड के लिए लीफ नोड्स की संख्या का पता लगाता है।
एक एन-आर्य पेड़ को देखते हुए, हमें प्रत्येक उपट्री के लिए लीफ नोड्स की संख्या का पता लगाना होगा। आइए एक उदाहरण देखें।
इनपुट
N = 8 tree = [[2, 3], [], [4, 5, 6], [7, 8], [], [], [], []]
आउटपुट
1->5 2->1 3->4 4->2 5->1 6->1 7->1 8->1
एल्गोरिदम
-
n-ary पेड़ की शुरुआत उस पेड़ से करें जिसे आप पसंद करते हैं।
-
पेड़ से गुजरने के लिए DFS का उपयोग करें।
-
प्रत्येक नोड लीफ नोड्स की संख्या को संग्रहीत करने के लिए एक सरणी बनाए रखें।
-
DFS को पुनरावर्ती कॉल के बाद लीफ नोड की संख्या बढ़ाएँ।
-
लीफ नोड्स काउंट के साथ सभी नोड प्रिंट करें।
कार्यान्वयन
C++ में उपरोक्त एल्गोरिथम का कार्यान्वयन निम्नलिखित है
#include <bits/stdc++.h>
using namespace std;
void insertNode(int x, int y, vector<int> tree[]) {
tree[x].push_back(y);
}
void DFS(int node, int leaf[], int visited[], vector<int> tree[]) {
leaf[node] = 0;
visited[node] = 1;
for (auto it : tree[node]) {
if (!visited[it]) {
DFS(it, leaf, visited, tree);
leaf[node] += leaf[it];
}
}
if (!tree[node].size()) {
leaf[node] = 1;
}
}
int main() {
int N = 8;
vector<int> tree[N + 1];
insertNode(1, 2, tree);
insertNode(1, 3, tree);
insertNode(3, 4, tree);
insertNode(3, 5, tree);
insertNode(3, 6, tree);
insertNode(4, 7, tree);
insertNode(4, 8, tree);
int leaf[N + 1];
int visited[N + 1];
for (int i = 0; i <= N; i++) {
visited[i] = 0;
}
DFS(1, leaf, visited, tree);
for (int i = 1; i <= N; i++) {
cout << i << "->" << leaf[i] << endl;
}
return 0;
} आउटपुट
यदि आप उपरोक्त कोड चलाते हैं, तो आपको निम्न परिणाम प्राप्त होंगे।
1->5 2->1 3->4 4->2 5->1 6->1 7->1 8->1