एक एन-आरी पेड़ और एक संख्या को देखते हुए, हमें दी गई संख्या से अधिक नोड्स की संख्या गिननी होगी। आइए एक उदाहरण देखें।
इनपुट
tree = [[4], [1, 2], [3, 5]] n = 2
आउटपुट
3
n से अधिक मान वाले 3 नोड हैं।
एल्गोरिदम
-
एन-आरी ट्री को इनिशियलाइज़ करें।
-
गिनती को 0 से प्रारंभ करें।
-
जब आप एक नोड पाते हैं जिसका मान n से अधिक है, तो गिनती को 1 से बढ़ाएँ।
-
वर्तमान नोड के बच्चे प्राप्त करें।
-
सभी बच्चों पर पुनरावृति करें और नोड्स गिनने के लिए समान फ़ंक्शन को बार-बार कॉल करें।
-
गिनती वापस करें।
कार्यान्वयन
C++ में उपरोक्त एल्गोरिथम का कार्यान्वयन निम्नलिखित है
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
vector<Node*> child;
};
Node* getNewNode(int data) {
Node* temp = new Node;
temp->data = data;
return temp;
}
int getGreaterElementsCount(Node* root, int n) {
if (root == NULL)
return 0;
int count = 0;
if (root->data > n) {
count++;
}
int nodeChildrenCount = root->child.size();
for (int i = 0; i < nodeChildrenCount; i++) {
Node* child = root->child[i];
count += getGreaterElementsCount(child, n);
}
return count;
}
int main() {
Node* root = getNewNode(1);
(root->child).push_back(getNewNode(2));
(root->child).push_back(getNewNode(3));
(root->child).push_back(getNewNode(4));
(root->child[0]->child).push_back(getNewNode(5));
(root->child[0]->child).push_back(getNewNode(5));
(root->child[1]->child).push_back(getNewNode(6));
(root->child[1]->child).push_back(getNewNode(6));
(root->child[1]->child).push_back(getNewNode(7));
(root->child[2]->child).push_back(getNewNode(8));
(root->child[2]->child).push_back(getNewNode(8));
(root->child[2]->child).push_back(getNewNode(9));
int n = 2;
cout << getGreaterElementsCount(root, n) << endl;
return 0;
} आउटपुट
यदि आप उपरोक्त कोड चलाते हैं, तो आपको निम्न परिणाम प्राप्त होंगे।
10