इस समस्या में हमें एक Binary tree दिया जाता है। हमारा कार्य पुनरावृत्ति और स्टैक के बिना का उपयोग किए बिना बाइनरी ट्री के पोस्टऑर्डर ट्रैवर्सल को प्रिंट करना है ।
बाइनरी ट्री एक विशेष प्रकार का पेड़ है जिसमें प्रत्येक नोड में अधिकतम 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<<"Post Order Traversal of the binary tree :\n";
postOrderTraversal(root);
return 0;
} आउटपुट
Post Order Traversal of the binary tree : 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<<"Post Order Traversal of the binary tree :\n";
postOrderTraversal(root);
return 0;
} आउटपुट
Post Order Traversal of the binary tree : 8 4 2 13 7 9 6