Giả sử chúng ta có một danh sách các phần tử trong một mảng, chúng ta phải kiểm tra xem các phần tử đó có thể là bộ truyền tải được sắp xếp trước của cây tìm kiếm nhị phân hay không. Giả sử một chuỗi giống như {40, 30, 35, 80, 100}, thì cây sẽ giống như -
Chúng tôi có thể giải quyết điều này bằng cách sử dụng một ngăn xếp. Chúng tôi phải làm theo các bước sau để giải quyết vấn đề này.
- Xác định ngăn xếp trống
- đặt gốc là vô cực âm
- đối với mọi phần tử trong trình tự đặt hàng trước, hãy thực hiện như sau -
- nếu phần tử nhỏ hơn gốc hiện tại, trả về false
- Tiếp tục xóa các phần tử khỏi ngăn xếp trong khi phần tử lớn hơn đỉnh ngăn xếp và đặt phần tử bị xóa cuối cùng làm phần tử gốc.
- đẩy phần tử vào ngăn xếp
Ví dụ
#include <iostream>
#include <stack>
using namespace std;
bool isValidPreorder(int pre[], int n) {
stack<int> stk;
int root = INT_MIN;
for (int i=0; i<n; i++) {
if (pre[i] < root)
return false;
while (!stk.empty() && stk.top()<pre[i]) {
root = stk.top();
stk.pop();
}
stk.push(pre[i]);
}
return true;
}
int main() {
int pre[] = {40, 30, 35, 80, 100};
int n = sizeof(pre)/sizeof(pre[0]);
if(isValidPreorder(pre, n))
cout << "This can form BST";
else
cout << "This can not form BST";
} Đầu ra
This can form BST