इस समस्या में हमें एक सरणी प्रीऑर्डर [] दिया जाता है जो बाइनरी सर्च ट्री के प्रीऑर्डर ट्रैवर्सल का प्रतिनिधित्व करता है। हमारा काम प्रीऑर्डर ट्रैवर्सल से बीएसटी के पोस्टऑर्डर ट्रैवर्सल का पता लगाना है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
preOrder[] = {5, 2, 4, 7, 12} आउटपुट
{4, 2, 12, 7, 5} समाधान दृष्टिकोण
समस्या का एक सरल समाधान दिए गए प्रीऑर्डर ट्रैवर्सल से एक BST बनाना है। और फिर पेड़ का पोस्टऑर्डर ट्रैवर्सल करें। यह समाधान ठीक है लेकिन एक अधिक प्रभावी समाधान है,
हम बाएं और दाएं सबट्री के मानों को अलग करने के लिए मानों की सीमा के साथ प्रीऑर्डर सरणी को पार करेंगे।
ट्रैवर्सल का क्रम है -
preOrder : Root -> Left -> Right postOrder : Left -> Right -> Root
प्रीऑर्डर में पहले तत्व के लिए जो मूल तत्व है। इसके लिए सीमा {INT_MIN, Root} है। फिर प्रीऑर्डर सरणी और पहले तत्व को पार करें और सीमा के अंतिम मान के साथ सभी तत्वों को सीमा में स्वैप करें। इसी तरह, हम इसे राइट सबट्री के लिए करेंगे और अंत में रूट जोड़ेंगे।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#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