พิมพ์ Postorder traversal จาก Inorder และ Preorder ที่กำหนด

ได้รับ Inorder และ Preorder traversal ของต้นไม้ ต้องหา Postorder traversal และพิมพ์ออกมา

Input:
Inorder:  {4, 2, 5, 1, 3, 6}
Preorder: {1, 2, 4, 5, 3, 6}
Output:
Postorder: {4, 5, 2, 6, 3, 1}

อัลกอริทึม

START
Step 1 -> declare function find_value(int p, int in_order[], int n)
    Loop For i=0 and i declare function postorder(int pre_order[], int in_order[], int n)
    Declare int 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 pre_order[] = {1, 2, 4, 5, 3, 6}
    Declare in_order[] = {4, 2, 5, 1, 3, 6}
    Declare size = sizeof(pre_order)/sizeof(pre_order[0])
    Call postorder(pre_order, in_order, size)
STOP

ตัวอย่างโค้ด (C)

#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