इस समस्या में हमें एक सरणी preOrder[] दी गई है जो बाइनरी सर्च ट्री के प्रीऑर्डर ट्रैवर्सल को दर्शाती है। हमारा कार्य प्रीऑर्डर ट्रैवर्सल से BST का पोस्टऑर्डर ट्रैवर्सल खोजना है।
आइए एक उदाहरण से इस समस्या को समझते हैं,
इनपुट
preOrder[] = {5, 2, 4, 7, 12}आउटपुट
{4, 2, 12, 7, 5}समाधान दृष्टिकोण
इस समस्या का एक सरल समाधान दिए गए प्रीऑर्डर ट्रैवर्सल से एक BST बनाना है। और फिर ट्री का पोस्टऑर्डर ट्रैवर्सल करना। यह समाधान ठीक है लेकिन एक अधिक प्रभावी समाधान है,
हम मानों पर एक सीमा के साथ प्रीऑर्डर सरणी को ट्रैवर्स करेंगे ताकि बाएं और दाएं सबट्री के मानों को अलग किया जा सके।
ट्रैवर्सल का क्रम है -
preOrder : रूट -> बाएं -> दाएं postOrder : बाएं -> दाएं -> रूट
प्रीऑर्डर में पहला तत्व जो रूट तत्व है। इसके लिए, सीमा {INT_MIN, रूट} है। फिर प्रीऑर्डर सरणी को ट्रैवर्स करें और पहले तत्व को सीमा में सभी तत्वों को सीमा के अंतिम मान के साथ स्वैप करें। इसी तरह, हम दाएं सबट्री के लिए ऐसा करेंगे और अंत में रूट जोड़ेंगे।
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
उदाहरण
#include <iostream> using namespace std; void findPostOrderTraversalRec(int pre[], int n, int lowerLimit, int upperLimit, int& index){ if (index == n) return; if (pre[index] < lowerLimit || pre[index] > upperLimit) return; int currNode = pre[index]; index++; findPostOrderTraversalRec(pre, n, lowerLimit, currNode, index); findPostOrderTraversalRec(pre, n, currNode, upperLimit, index); cout<<currNode<<" "; } void findPostOrderTraversalFromPreOrder(int pre[], int n){ int index = 0; findPostOrderTraversalRec(pre, n, -1000, 1000, index); } int main(){ int pre[] = { 5, 2, 4, 7, 12 }; int n = sizeof(pre) / sizeof(pre[0]); cout<<"PreOrder Traversal : \t"; for(int i = 0; i < n ; i++) cout<<pre[i]<<" "; cout<<endl<<"Post Order Traversal : \t"; findPostOrderTraversalFromPreOrder(pre, n); return 0; }आउटपुट
PreOrder Traversal - 5 2 4 7 12 Post Order Traversal - 4 2 12 7 5
समस्या को हल करने की एक और विधि पुनरावृत्ति का उपयोग करना है। जैसा कि हम जानते हैं कि प्रीऑर्डर रूट -> बाएं -> दाएं है और पोस्टऑर्डर बाएं -> दाएं -> रूट है। इसकी गणना एक लूप और पिवट तत्व की गणना करके की जा सकती है जो वह स्थान है जहां बाएं तत्व का अंतिम तत्व है। इसका उपयोग करके हम पहले बाएं, फिर दाएं और फिर रूट प्रिंट करेंगे।
पिवट को रूट से छोटे बड़े तत्व का इंडेक्स ढूंढकर पाया जाता है।
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
उदाहरण
#include <iostream> using namespace std; void findPostOrderTraversalFromPreOrder(int pre[], int n){ int pivot = 0; for(int i = 1; i < n; i++){ if (pre[0] <= pre[i]) { pivot = i; break; } } for(int i = pivot - 1; i > 0; i--){ cout << pre[i] << " "; } for(int i = n - 1; i >= pivot; i--) { cout << pre[i] << " "; } cout << pre[0]; } int main(){ int pre[] = { 5, 2, 4, 7, 12 }; int n = sizeof(pre) / sizeof(pre[0]); cout<<"PreOrder Traversal : \t"; for(int i = 0; i < n ; i++) cout<<pre[i]<<" "; cout<<endl<<"Post Order Traversal : \t"; findPostOrderTraversalFromPreOrder(pre, n); return 0; }आउटपुट
PreOrder Traversal - 5 2 4 7 12 Post Order Traversal - 4 2 12 7 5
