เรามีอาร์เรย์ A เราต้องตรวจสอบว่าอาร์เรย์สามารถแสดง BST ที่มีระดับ n ได้หรือไม่ ตามระดับที่กำหนด เราสามารถสร้างต้นไม้ในลักษณะดังต่อไปนี้ สมมติว่าตัวเลขคือ k ค่าที่มากกว่า k จะเลื่อนไปทางขวา และน้อยกว่า k จะเคลื่อนที่ไปทางซ้าย สมมติว่ามี 2 รายการ:{50, 20, 9, 25, 10} และ {50, 30, 20, 25, 10}
อันแรกไม่ถูกต้อง แต่อันที่สองใช้ได้
ในการตรวจสอบนี้ เราสามารถสร้าง BST และตรวจสอบความสูง มิฉะนั้น ให้ใช้วิธีการแบบอาร์เรย์ วิธีการตามอาร์เรย์เป็นเหมือนด้านล่าง -
- ใช้ตัวแปร max =อินฟินิตี้สองตัว เพื่อทำเครื่องหมายขีดจำกัดสูงสุดของทรีย่อยด้านซ้าย และ min =อินฟินิตี้เชิงลบเพื่อทำเครื่องหมายขีดจำกัดต่ำสุดสำหรับทรีย่อยด้านขวา
- สำหรับแต่ละองค์ประกอบในช่วง arr[i] ถึง arr[n – 1] ทำซ้ำขั้นตอนต่อไปนี้
- ถ้า arr[i]> arr[i - 1] และ arr[i]> min และ arr[i]
- มิฉะนั้น ถ้า arr[i]> min และ arr[i]
- ถ้าสิ่งเหล่านี้ไม่ถูกต้อง องค์ประกอบจะถูกแทรกเข้าไปในระดับใหม่ ดังนั้นให้แตก
- มิฉะนั้น ถ้า arr[i]> min และ arr[i]
- ถ้า arr[i]> arr[i - 1] และ arr[i]> min และ arr[i]
ตัวอย่าง
#include <iostream>
using namespace std;
bool canMakeBSTifHeightN(int arr[], int n) {
int min = INT_MIN;
int max = INT_MAX;
for(int i = 1; i < n; i++){
if (arr[i] > arr[i - 1] && arr[i] > min && arr[i] < max) {
min = arr[i - 1];
} else if (arr[i] < arr[i - 1] && arr[i] > min && arr[i] <
max) {
max = arr[i - 1];
} else {
return true;
}
}
return false;
}
int main() {
int elements[] = {50, 30, 20, 25, 10};
int n = sizeof(elements)/sizeof(elements[0]);
if (canMakeBSTifHeightN(elements, n))
cout << "We can make BST of height " << n;
else
cout << "We can not make BST of height " << n;
} ผลลัพธ์
We can make BST of height 5
