n-আরি গাছ হল প্রতিটি নোডের জন্য n শিশু সহ গাছ। আমাদের একটি সংখ্যা n দেওয়া হয়েছে এবং আমাদের n-আরি ট্রি থেকে পরবর্তী বড় উপাদানটি খুঁজে বের করতে হবে।
আমরা 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
