একটি ট্রির ইনঅর্ডার এবং প্রিঅর্ডার দেওয়া আছে। প্রোগ্রামটি পোস্টঅর্ডার ট্রাভার্সাল বের করে প্রিন্ট করবে।
Input: Inorder traversal in[] = {4, 2, 5, 1, 3, 6} Preorder traversal pre[] = {1, 2, 4, 5, 3, 6} Output: Postorder traversal post[] = {4, 5, 2, 6, 3, 1}অ্যালগরিদম
START Step 1 -> declare function as find_value(int p, int in_order[], int n) Loop For i=0 and ideclare function as postorder(int pre_order[], int in_order[], int n) Declare int variable as root = find_value(pre_order[0], in_order, n) IF root!=0 Call postorder(pre_order+1, in_order, root) End IF root !=n-1 Call postorder(pre_order+root+1, in_order+root+1,n-root-1) End Print pre_order[0] End Step 3 -> goto main() Declare int pre_order[] = {1, 2, 4, 5, 3, 6} Declare int in_order[] = {4, 2, 5, 1, 3, 6} Declare int size = sizeof(pre_order)/sizeof(pre_order[0]) Call postorder(pre_order, in_order, size) STOP
উদাহরণ
#include <stdio.h> int find_value(int p, int in_order[], int n) { for (int i = 0; i < n; ++i) { if (in_order[i] == p) { return i; } } return -1; } int postorder(int pre_order[], int in_order[], int n) { int root = find_value(pre_order[0], in_order, n); if(root !=0 ) postorder(pre_order+1, in_order, root); if (root != n-1) postorder(pre_order+root+1, in_order+root+1, n-root-1); printf("%d ", pre_order[0]); } int main(int argc, char const *argv[]) { int pre_order[] = {1, 2, 4, 5, 3, 6}; int in_order[] = {4, 2, 5, 1, 3, 6}; int size = sizeof(pre_order)/sizeof(pre_order[0]); postorder(pre_order, in_order, size); return 0; }আউটপুট
যদি উপরের প্রোগ্রামটি রান করি তবে নিচের আউটপুট জেনারেট হবে
4 5 2 6 3 1
