इस समस्या में, हमें एक N-एरी ट्री दिया गया है। हमारा कार्य ट्री का प्रीऑर्डर ट्रैवर्सल प्रिंट करना है।
पहले, आइए कुछ बुनियादी शब्दावली सीखें,
N-एरी ट्री एक ट्री है जिसमें सभी नोड्स में अधिकतम N चाइल्ड नोड्स हो सकते हैं। उदाहरण 2-एरी (बाइनरी) ट्री में अधिकतम 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
