इस ट्यूटोरियल में, हम एक प्रोग्राम लिखने जा रहे हैं जो n-ary ट्री में प्रत्येक नोड के लिए लीफ नोड्स की संख्या ढूंढता है।
एक 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
