এই সমস্যায়, আমাদের একটি N-ary Tree দেওয়া হয়। আমাদের কাজ হল গাছের প্রি-অর্ডার ট্রাভার্সাল প্রিন্ট করা।
প্রথমে, আসুন কিছু মৌলিক পরিভাষা শিখি,
N-ary গাছ একটি গাছ যেখানে সমস্ত নোডের সর্বোচ্চ N চাইল্ড নোড থাকতে পারে। উদাহরণ 2-ary (বাইনারি) গাছে সর্বাধিক 2টি চাইল্ড নোড রয়েছে৷
৷প্রাক-অর্ডার ট্রাভার্সাল গাছের নোড অতিক্রম করার একটি উপায়। এতে আমরা প্রথমে রুট নোড তারপর লেফট চাইল্ড এবং তারপর রাইট চাইল্ড অতিক্রম করব।
আমাদের সমস্যা বোঝার জন্য একটি উদাহরণ নেওয়া যাক
Preorder traversal : 12151499411719
এই সমস্যা সমাধানের জন্য, আমাদের স্ট্যাক ডেটা স্ট্রাকচার ব্যবহার করতে হবে। আমরা প্রথমে রুট নোডকে স্ট্যাকের দিকে ঠেলে দেব। তারপর এটি পপ এবং এটি মুদ্রণ. প্রতিটি পপড নোডের জন্য, আমরা স্ট্যাকের চাইল্ড নোডগুলিকে ডান চাইল্ড থেকে বাম চাইল্ডে ঠেলে দেব। তারপর পপ যখন সমস্ত চাইল্ড নোড পুশ করা হয়। স্ট্যাক খালি না হওয়া পর্যন্ত এই প্রক্রিয়াটি পুনরাবৃত্তি করুন।
আমাদের সমাধানের বাস্তবায়ন দেখানোর জন্য প্রোগ্রাম
উদাহরণ
#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(struct Node* root){
stack<Node*> tree;
tree.push(root);
while (!tree.empty()) {
Node* curr = tree.top();
tree.pop();
cout<<curr->key<<"\t";
vector<Node*>::iterator it = curr->child.end();
while (it != curr->child.begin()) {
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 14 25 99 4 11 7 19
