सी++ में एन-आरी ट्री में अगला बड़ा तत्व

एन-आर्य पेड़ प्रत्येक नोड के लिए एन बच्चों वाला पेड़ है। हमें एक संख्या n दी गई है और हमें n-ary पेड़ से अगला बड़ा तत्व खोजना है।

हम n-ary पेड़ को पार करके और परिणाम को बनाए रखते हुए समाधान ढूंढ सकते हैं।

एल्गोरिदम

• एन-एरी ट्री बनाएं।
• परिणाम प्रारंभ करें।
• अगला बड़ा तत्व प्राप्त करने के लिए एक फ़ंक्शन लिखें।
  • यदि वर्तमान नोड शून्य है तो वापस लौटें।
  • जांचें कि वर्तमान नोड डेटा अपेक्षित तत्व से अधिक है या नहीं।
  • यदि हां, तो जांचें कि क्या परिणाम खाली है या परिणाम वर्तमान नोड डेटा से अधिक है।
  • यदि उपरोक्त शर्त पूरी होती है, तो परिणाम अपडेट करें।
  • वर्तमान नोड बच्चे प्राप्त करें।
  • बच्चों पर पुनरावृति करें।
    • पुनरावर्ती फ़ंक्शन को कॉल करें।

हम हर बार परिणाम को अपडेट कर रहे हैं जब हमें कोई ऐसा तत्व मिलता है जो दी गई संख्या से बड़ा और परिणाम से कम होता है। यह सुनिश्चित करता है कि हमें अंत में अगला बड़ा तत्व मिले।

कार्यान्वयन

C++ में उपरोक्त एल्गोरिथम का कार्यान्वयन निम्नलिखित है

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   vector<Node*> child;
};
Node* newNode(int data) {
   Node* newNode = new Node;
   newNode->data = data;
   return newNode;
}
void findNextGreaterElement(Node* root, int x, Node** result) {
   if (root == NULL) {
      return;
   }
   if (root->data > x) {
      if (!(*result) || (*result)->data > root->data) {
         *result = root;
      }
   }
   int childCount = root->child.size();
   for (int i = 0; i < childCount; i++) {
      findNextGreaterElement(root->child[i], x, result);
   }
   return;
}
int main() {
   Node* root = newNode(10);
   root->child.push_back(newNode(12));
   root->child.push_back(newNode(23));
   root->child.push_back(newNode(45));
   root->child[0]->child.push_back(newNode(40));
   root->child[1]->child.push_back(newNode(33));
   root->child[2]->child.push_back(newNode(12));
   Node* result = NULL;
   findNextGreaterElement(root, 20, &result);
   cout << result->data << endl;
   return 0;
}

आउटपुट

यदि आप उपरोक्त कोड चलाते हैं, तो आपको निम्न परिणाम प्राप्त होंगे।

23