In duyệt hậu thứ tự từ duyệt trung thứ tự và tiền thứ tự cho trước

Cho duyệt trung thứ tự (inorder) và tiền thứ tự (preorder) của một cây, chương trình phải tìm duyệt hậu thứ tự (postorder) và in ra.

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 -> khai báo function as find_value(int p, int in_order[], int n)
  Vòng lặp For i=0 and i<n and ++i
    IF in_order[i]==p
      Return i
    End IF
  End
Step 2 -> khai báo function as postorder(int pre_order[], int in_order[], int n)
  Khai báo 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()
  Khai báo int pre_order[] = {1, 2, 4, 5, 3, 6}
  Khai báo int in_order[] = {4, 2, 5, 1, 3, 6}
  Khai báo 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;
}

Kết quả

Nếu chúng ta chạy chương trình trên thì nó sẽ tạo ra đầu ra sau

4 5 2 6 3 1