এই সমস্যাতে, একটি বাইনারি ট্রির ইনঅর্ডার (inorder) এবং পোস্টঅর্ডার (postorder) ট্রাভার্সাল দেওয়া থাকে। ট্রির প্রিঅর্ডার (preorder) ট্রাভার্সাল প্রিন্ট করতে হবে।
উদাহরণ
Inorder: 16 7 21 12 1 5 9 Postorder: 16 21 7 1 9 5 12 Preorder: 12 7 16 21 5 1 9
অ্যালগরিদম (স্ট্যাক ব্যবহার)
- পোস্টঅর্ডারের শেষ উপাদানই রুট
- ইনঅর্ডারে রুট খুঁজে বাম ও ডান সাবট্রি আলাদা করুন
- রিকার্সিভলি প্রসেস করুন: ডান সাবট্রি → বাম সাবট্রি → রুট (স্ট্যাকে পুশ)
- স্ট্যাকে পপ করলে প্রিঅর্ডার পাওয়া যাবে
C++ প্রোগ্রাম উদাহরণ (জাভা কোড অনুবাদ)
#include <bits/stdc++.h>
using namespace std;
static int postIndex;
void preOrder(int in[], int post[], int inStrt, int inEnd, stack<int> &preorder) {
if (inStrt > inEnd) return;
int val = post[postIndex];
int inIndex = -1;
for (int i = inStrt; i <= inEnd; i++)
if (in[i] == val) { inIndex = i; break; }
postIndex--;
preOrder(in, post, inIndex + 1, inEnd, preorder); // ডান
preOrder(in, post, inStrt, inIndex - 1, preorder); // বাম
preorder.push(val);
}
void printPreOrderTraversal(int in[], int post[], int n) {
postIndex = n - 1;
stack<int> preorder;
preOrder(in, post, 0, n - 1, preorder);
while (!preorder.empty()) {
cout << preorder.top() << " ";
preorder.pop();
}
}
int main() {
int in[] = {4, 10, 12, 15, 18, 22, 24, 25, 31, 35, 44, 50, 66, 70, 90};
int post[] = {4, 12, 10, 18, 24, 22, 15, 31, 44, 35, 66, 90, 70, 50, 25};
int n = sizeof(in) / sizeof(in[0]);
cout << "Preorder Traversal of the tree is: ";
printPreOrderTraversal(in, post, n);
return 0;
}
আউটপুট
Preorder Traversal of the tree is: 25 15 10 4 12 22 18 24 50 35 31 44 70 66 90
