주어진 Inorder 및 Preorder 순회에서 Postorder 순회 인쇄

트리 프로그램의 inorder 및 preorder와 함께 제공되면 postroder 순회를 찾고 동일하게 인쇄해야 합니다.

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 i<n and ++i
      IF in_order[i]==p
         Return i
      End IF
   End
Step 2 -> declare 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