Tìm duyệt hậu tự (postorder) của BST từ duyệt tiền tự (preorder) trong C++

Trong bài toán này, cho mảng preOrder[] biểu diễn duyệt tiền tự của cây tìm kiếm nhị phân (BST). Nhiệm vụ là tìm duyệt hậu tự của BST từ duyệt tiền tự.

Ví dụ minh họa:

Đầu vào

preOrder[] = {5, 2, 4, 7, 12}

Đầu ra

{4, 2, 12, 7, 5}

Phương pháp giải

Cách 1: Xây BST từ preorder, rồi duyệt postorder. Cách 2 hiệu quả hơn: Duyệt preorder với giới hạn giá trị phân tách cây con trái/phải.

Thứ tự: preOrder: Root -> Left -> Right. postOrder: Left -> Right -> Root.

Phần tử đầu preorder là root. Giới hạn {INT_MIN, Root}. Duyệt preorder, đổi chỗ phần tử trong giới hạn với cuối giới hạn. Tương tự cho cây con phải, thêm root cuối cùng.

Chương trình minh họa (Đệ quy):

Ví dụ

#include <iostream> 
using namespace std; 

void findPostOrderTraversalRec(int pre[], int n, int lowerLimit, int upperLimit, int& index){ 
    if (index == n) return; 
    if (pre[index] < lowerLimit || pre[index] > upperLimit) return; 
    int currNode = pre[index]; 
    index++; 
    findPostOrderTraversalRec(pre, n, lowerLimit, currNode, index); 
    findPostOrderTraversalRec(pre, n, currNode, upperLimit, index); 
    cout<<currNode<<" "; 
} 

void findPostOrderTraversalFromPreOrder(int pre[], int n){ 
    int index = 0; 
    findPostOrderTraversalRec(pre, n, -1000, 1000, index); 
} 

int main(){ 
    int pre[] = { 5, 2, 4, 7, 12 }; 
    int n = sizeof(pre) / sizeof(pre[0]); 
    cout<<"PreOrder Traversal : \t"; 
    for(int i = 0; i < n ; i++) cout<<pre[i]<<" "; 
    cout<<endl<<"Post Order Traversal : \t"; 
    findPostOrderTraversalFromPreOrder(pre, n); 
    return 0; 
}

Kết quả

PreOrder Traversal - 5 2 4 7 12 Post Order Traversal - 4 2 12 7 5

Cách 3 (Lặp): preorder = root-left-right, postorder = left-right-root. Tìm pivot (phần tử đầu tiên > root). In left (pivot-1 đến 1), in right (n-1 đến pivot), in root.

Chương trình minh họa (Lặp):

Ví dụ

#include <iostream> 
using namespace std; 

void findPostOrderTraversalFromPreOrder(int pre[], int n){ 
    int pivot = 0; 
    for(int i = 1; i < n; i++){ 
        if (pre[0] <= pre[i]) { pivot = i; break; } 
    } 
    for(int i = pivot - 1; i > 0; i--) cout << pre[i] << " "; 
    for(int i = n - 1; i >= pivot; i--) cout << pre[i] << " "; 
    cout << pre[0]; 
} 

int main(){ 
    int pre[] = { 5, 2, 4, 7, 12 }; 
    int n = sizeof(pre) / sizeof(pre[0]); 
    cout<<"PreOrder Traversal : \t"; 
    for(int i = 0; i < n ; i++) cout<<pre[i]<<" "; 
    cout<<endl<<"Post Order Traversal : \t"; 
    findPostOrderTraversalFromPreOrder(pre, n); 
    return 0; 
}

Kết quả

PreOrder Traversal - 5 2 4 7 12 Post Order Traversal - 4 2 12 7 5