इस समस्या में, हमें एक बाइनरी ट्री दिया गया है। हमारा कार्य बाइनरी ट्री के पोस्टऑर्डर ट्रैवर्सल को रिकर्सन और स्टैक का उपयोग किए बिना प्रिंट करना है।
बाइनरी ट्री एक विशेष प्रकार का ट्री है जिसमें प्रत्येक नोड में अधिकतम 2 चाइल्ड नोड हो सकते हैं।
पोस्टऑर्डर ट्रैवर्सल एक ट्री ट्रैवर्सल तकनीक है, जिसमें पहले बाएं सबट्री को पार किया जाता है, फिर दाएं सबट्री को और अंत में रूट को पार किया जाता है।
उपरोक्त ट्री का पोस्टऑर्डर ट्रैवर्सल - 8 4 2 7 9 6
रिकर्सन और स्टैक का उपयोग किए बिना ट्री को पार करने के लिए। हम डेप्थ-फर्स्ट सर्च आधारित तकनीक का उपयोग करेंगे और डेटा को हैश टेबल में संग्रहीत करेंगे।
उदाहरण
इस समाधान के कार्यान्वयन को दर्शाने वाला प्रोग्राम,
#include <bits/stdc++.h> using namespace std; struct Node { int data; struct Node *left, *right; }; void postOrderTraversal(struct Node* head) { struct Node* temp = head; unordered_set<Node*> visited; while (temp && visited.find(temp) == visited.end()) { if (temp->left && visited.find(temp->left) == visited.end()) temp = temp->left; else if (temp->right && visited.find(temp->right) == visited.end()) temp = temp->right; else { cout<<temp->data<<"\t"; visited.insert(temp); temp = head; } } } struct Node* insertNode(int data){ struct Node* node = new Node; node->data = data; node->left = NULL; node->right = NULL; return (node); } int main(){ struct Node* root = insertNode(6); root->left = insertNode(2); root->right = insertNode(9); root->left->left = insertNode(8); root->left->right = insertNode(4); root->right->left = insertNode(7); root->right->left->left = insertNode(13); cout<<"बाइनरी ट्री का पोस्ट ऑर्डर ट्रैवर्सल :\n"; postOrderTraversal(root); return 0; }आउटपुट
बाइनरी ट्री का पोस्ट ऑर्डर ट्रैवर्सल : 8 4 2 13 7 9 6
इसी समाधान को अपडेट किया जा सकता है और हैश टेबल के उपयोग को समाप्त किया जा सकता है। चूंकि इसका काम विज़िट किए गए नोड्स को स्टोर करना है। हम ट्री में प्रत्येक नोड पर एक विज़िटेड फ्लैग जोड़ देंगे ताकि सिस्टम पर लोड कम हो, यह हमारे एल्गोरिदम को बेहतर बनाएगा।
एक अधिक प्रभावी समाधान अनऑर्डर्ड मैप का उपयोग करना है, यह हेड पर वापस ट्रैक करने के ओवरहेड को कम करेगा।
उदाहरण
कार्यान्वयन को दर्शाने वाला प्रोग्राम
#include <bits/stdc++.h> using namespace std; struct Node { int data; struct Node *left, *right; bool visited; }; void postOrderTraversal(Node* root) { Node* n = root; unordered_map<Node*, Node*> postorder; postorder.insert(pair<Node*, Node*>(root, nullptr)); while (n) { if (n->left && postorder.find(n->left) == postorder.end()) { postorder.insert(pair<Node*, Node*>(n->left, n)); n = n->left; } else if (n->right && postorder.find(n->right) == postorder.end()) { postorder.insert(pair<Node*, Node*>(n->right, n)); n = n->right; } else { cout<<n->data<<"\t"; n = (postorder.find(n))->second; } } } struct Node* insertNode(int data) { struct Node* node = new Node; node->data = data; node->left = NULL; node->right = NULL; node->visited = false; return (node); } int main() { struct Node* root = insertNode(6); root->left = insertNode(2); root->right = insertNode(9); root->left->left = insertNode(8); root->left->right = insertNode(4); root->right->left = insertNode(7); root->right->left->left = insertNode(13); cout<<"बाइनरी ट्री का पोस्ट ऑर्डर ट्रैवर्सल :\n"; postOrderTraversal(root); return 0; }आउटपुट
बाइनरी ट्री का पोस्ट ऑर्डर ट्रैवर्सल : 8 4 2 13 7 9 6
