এই সমস্যায় আমাদের একটি অ্যারে প্রিঅর্ডার [] দেওয়া হয়েছে যা বাইনারি সার্চ ট্রির প্রিঅর্ডার ট্রাভার্সালকে প্রতিনিধিত্ব করে। আমাদের কাজ হল প্রি-অর্ডার ট্রাভার্সাল থেকে BST-এর পোস্টঅর্ডার ট্রাভার্সাল খুঁজে বের করা।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
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
