Cây nhị phân là một cấu trúc dữ liệu dạng cây, trong đó có hai nút con cho mỗi nút. Các nút con là hai được gọi là nút con bên trái và bên phải.
BST là một cấu trúc cây, trong đó cây con bên trái chứa các nút có giá trị nhỏ hơn giá trị gốc và cây con bên phải chứa các nút có giá trị lớn hơn gốc đó.
Ở đây, chúng tôi sẽ kiểm tra xem cây nhị phân có phải là một BST hay không -
Để kiểm tra điều này, chúng ta phải kiểm tra điều kiện BST trên cây nhị phân. Đối với kiểm tra nút gốc cho nút con bên trái phải nhỏ hơn gốc đó, nút con phải lớn hơn gốc đó cho tất cả các nút của cây mà nút con tồn tại.
CHƯƠNG TRÌNH KIỂM TRA MỘT CÂY BINARY CÓ PHẢI LÀ BST
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
class node {
public:
int data;
node* left;
node* right;
node(int data) {
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
int isBSTUtil(node* node, int min, int max);
int isBST(node* node) {
return(isBSTUtil(node, INT_MIN, INT_MAX));
}
int isBSTUtil(node* node, int min, int max) {
if (node==NULL)
return 1;
if (node->data < min || node->data > max)
return 0;
return
isBSTUtil(node->left, min, node->data-1) && isBSTUtil(node->right, node->data+1, max);
}
int main() {
node *root = new node(8);
root->left = new node(3);
root->right = new node(10);
root->left->left = new node(1);
root->left->right = new node(6);
if(isBST(root))
cout<<"The given tree is a BST";
else
cout<<"The given tree is Not a BST";
return 0;
} Đầu ra
The given tree is a BST
Giải thích mã
Mã trên kiểm tra một BST. Phương thức main, tạo một cây và gọi phương thức isBST (). Phương pháp này kiểm tra xem con bên trái và bên phải có tuân theo quy tắc BST hay không và các cây con được tạo thành cũng là BST bằng cách sử dụng phương thức isBSTuntil ().