In đường truyền Postorder từ các đường truyền Inorder và Đặt hàng trước đã cho

Được đưa ra với inorder và đặt hàng trước của một chương trình cây phải tìm trình duyệt postroder và in cùng một

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}

Thuật toán

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

Ví dụ

#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;
}

Đầu ra

nếu chúng ta chạy chương trình trên thì nó sẽ tạo ra kết quả sau

4 5 2 6 3 1