এই সমস্যাতে, একটি N-এরি ট্রি (N-ary Tree) দেওয়া থাকে। রিকার্শন ব্যবহার না করে এর প্রিঅর্ডার ট্রাভার্সাল প্রিন্ট করতে হবে।
বেসিক ধারণা
- N-এরি ট্রি: প্রতিটি নোডের সর্বোচ্চ Nটি চাইল্ড হতে পারে (বাইনারি ট্রি = 2-এরি)
- প্রিঅর্ডার: রুট → বাম থেকে ডান ক্রমে চাইল্ডগুলো
স্ট্যাক ভিত্তিক অ্যালগরিদম
- রুট নোড স্ট্যাকে পুশ করুন
- স্ট্যাক খালি না হওয়া পর্যন্ত:
- টপ নোড পপ করুন এবং প্রিন্ট করুন
- তার চাইল্ডগুলো ডান থেকে বাম ক্রমে স্ট্যাকে পুশ করুন
C++ প্রোগ্রাম উদাহরণ
#include <bits/stdc++.h>
using namespace std;
struct Node {
int key;
vector<Node*> child;
};
Node* insertNode(int key) {
Node* temp = new Node;
temp->key = key;
return temp;
}
void preOrderTraversal(Node* root) {
stack<Node*> tree;
tree.push(root);
while (!tree.empty()) {
Node* curr = tree.top(); tree.pop();
cout << curr->key << "\t";
// চাইল্ডগুলো রাইট-টু-লেফ্ট পুশ করুন
for (auto it = curr->child.rbegin(); it != curr->child.rend(); ++it)
tree.push(*it);
}
}
int main() {
Node* root = insertNode(12);
root->child.push_back(insertNode(15));
root->child.push_back(insertNode(99));
root->child.push_back(insertNode(4));
root->child.push_back(insertNode(7));
root->child[0]->child.push_back(insertNode(1));
root->child[0]->child.push_back(insertNode(4));
root->child[0]->child.push_back(insertNode(25));
root->child[2]->child.push_back(insertNode(11));
root->child[3]->child.push_back(insertNode(19));
cout << "PreOrder Traversal of the tree is:\n";
preOrderTraversal(root);
return 0;
}
আউটপুট
PreOrder Traversal of the tree is: 12 15 1 4 25 99 4 11 7 19
