Kiểm tra mảng đã cho có kích thước n có thể đại diện cho BST gồm n cấp hay không trong C ++

Chúng ta có một mảng A, chúng ta phải kiểm tra xem mảng có thể biểu diễn một BST có n cấp hay không. Theo cấp độ, chúng ta có thể xây dựng một cây theo cách sau. Giả sử một số là k, giá trị lớn hơn k chuyển sang vế phải và nhỏ hơn k chuyển sang vế trái. Giả sử có hai danh sách:{50, 20, 9, 25, 10} và {50, 30, 20, 25, 10}

Cái đầu tiên không hợp lệ, nhưng cái thứ hai hợp lệ.

Để kiểm tra điều này, chúng ta có thể tạo BST và kiểm tra chiều cao, nếu không thì sử dụng phương pháp dựa trên mảng. Phương pháp dựa trên mảng giống như bên dưới -

• Lấy hai biến max =infinity để đánh dấu giới hạn tối đa của cây con bên trái và min =âm vô cùng để đánh dấu giới hạn tối thiểu cho cây con bên phải
• đối với mỗi phần tử trong dải ô arr [i] đến arr [n - 1], hãy lặp lại các bước sau
  • nếu arr [i]> arr [i - 1] và arr [i]> min và arr [i]
  • ngược lại nếu arr [i]> min và arr [i]
  • nếu không có cái nào trong số này hợp lệ, thì phần tử sẽ được chèn vào một cấp mới, vì vậy hãy ngắt

Ví dụ

#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;
}

Đầu ra

We can make BST of height 5