สมมติว่าเรามีรายการองค์ประกอบในอาร์เรย์ เราต้องตรวจสอบว่าองค์ประกอบดังกล่าวสามารถเป็นแบบสั่งผ่านล่วงหน้าของทรีการค้นหาแบบไบนารีหรือไม่ สมมติว่าลำดับเป็นเหมือน {40, 30, 35, 80, 100} จากนั้นต้นไม้จะเป็นเช่น −
เราสามารถแก้ปัญหานี้โดยใช้สแต็ค เราต้องทำตามขั้นตอนเหล่านี้เพื่อแก้ปัญหานี้
- กำหนดสแต็กว่าง
- กำหนดรูทเป็นลบอินฟินิตี้
- สำหรับทุกองค์ประกอบในลำดับการสั่งซื้อล่วงหน้า ให้ทำดังต่อไปนี้ −
- หากองค์ประกอบมีขนาดเล็กกว่ารูทปัจจุบัน ให้คืนค่าเท็จ
- ลบองค์ประกอบออกจากสแต็กต่อไปในขณะที่องค์ประกอบนั้นมากกว่าสแต็กบน และทำให้องค์ประกอบที่ถูกลบล่าสุดเป็นรูท
- ผลักองค์ประกอบลงในสแต็ก
ตัวอย่าง
#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";
} ผลลัพธ์
This can form BST
