सी ++ में बिना रिकर्सन के एन-आरी ट्री का प्रीऑर्डर ट्रैवर्सल

इस समस्या में हमें एक N-ary Tree दिया जाता है। हमारा काम ट्री के प्रीऑर्डर ट्रैवर्सल को प्रिंट करना है।

सबसे पहले, आइए कुछ बुनियादी शब्दावली सीखें,

एन-आरी ट्री एक पेड़ है जिसमें सभी नोड्स में अधिकतम एन चाइल्ड नोड्स हो सकते हैं। उदाहरण 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