Trong bài toán này, chúng ta được cung cấp một mảng preOrder [] đại diện cho việc truyền tải trước của cây tìm kiếm nhị phân. Nhiệm vụ của chúng tôi là Tìm truyền tải của BST từ đơn đặt hàng trước.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
preOrder[] = {5, 2, 4, 7, 12} Đầu ra
{4, 2, 12, 7, 5} Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là tạo một BST từ truyền tải đặt hàng trước đã cho. Và sau đó đi ngang qua thứ tự của cây. Giải pháp này không sao nhưng giải pháp hiệu quả hơn là,
Chúng tôi sẽ duyệt qua mảng đặt hàng trước với giới hạn về giá trị để tách các giá trị của cây con bên trái và bên phải.
Thứ tự chuyển tải là -
preOrder : Root -> Left -> Right postOrder : Left -> Right -> Root
Đối với phần tử đầu tiên được đặt hàng trước là phần tử gốc. Đối với điều này, giới hạn là {INT_MIN, Root}. Sau đó duyệt qua mảng đặt hàng trước và phần tử đầu tiên và hoán đổi tất cả các phần tử trong giới hạn với giá trị cuối cùng của giới hạn. Tương tự, chúng ta sẽ làm điều này cho cây con bên phải và thêm gốc vào cuối.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
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;
} Đầu ra
PreOrder Traversal − 5 2 4 7 12 Post Order Traversal − 4 2 12 7 5
Một phương pháp nữa để giải quyết vấn đề là sử dụng phép lặp. Như chúng ta biết rằng preorder trong root -> left -> right và postOrder là left -> right -> root. Điều này có thể được tính toán bằng cách sử dụng một vòng lặp và tính toán phần tử pivot là nơi chứa phần tử cuối cùng của phần tử bên trái. Sử dụng điều này, chúng tôi sẽ in bên trái đầu tiên, sau đó bên phải và sau đó là thư mục gốc.
Trụ được tìm thấy bằng cách tìm chỉ mục của phần tử lớn hơn nhỏ hơn gốc đó.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
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;
} Đầu ra
PreOrder Traversal − 5 2 4 7 12 Post Order Traversal − 4 2 12 7 5