Cây tìm kiếm nhị phân là một cấu trúc dữ liệu cây nhị phân trong đó chúng ta có 3 thuộc tính -
-
Cây con bên trái của cây tìm kiếm nhị phân của một nút chỉ chứa các nút có khóa nhỏ hơn khóa của nút.
-
Cây con bên phải của nút cây tìm kiếm nhị phân chỉ chứa các nút có khóa lớn hơn khóa của nút.
-
Bên trái và bên phải của một cây con, mỗi cây cũng phải là một cây tìm kiếm nhị phân.
Thuật toán
Begin function BSTUtill() If node is equals to NULL then Return 1. If data of node is less than minimum or greater than maximum data then Return 0. Traverse left and right sub-trees recursively. End.
Mã mẫu
#include <iostream>
#include <cstdlib>
#include <climits>
using namespace std;
struct n {
int d;
n* l;
n* r;
};
int BSTUtil(n* node, int min, int max);
int isBST(n* node) {
return(BSTUtil(node, INT_MIN, INT_MAX));
}
int BSTUtil(struct n* node, int min, int max) {
if (node==NULL)
return 1;
if (node->d < min || node->d > max)
return 0;
return BSTUtil(node->l, min, node->d - 1) && BSTUtil(node->r, node->d + 1, max);
}
n* newN(int d) {
n* nod = new n;
nod->d = d;
nod->l = NULL;
nod->r = NULL;
return nod;
}
int main() {
n *root = newN(7);
root->l = newN(6);
root->r = newN(10);
root->l->l = newN(2);
root->l->r = newN(4);
if (isBST(root))
cout<<"The Given Binary Tree is a BST"<<endl;
else
cout<<"The Given Binary Tree is not a BST"<<endl;
n *root1 = newN(10);
root1->l = newN(6);
root1->r = newN(11);
root1->l->l = newN(2);
root1->l->r = newN(7);
if (isBST(root1))
cout<<"The Given Binary Tree is a BST"<<endl;
else
cout<<"The Given Binary Tree is not a BST"<<endl;
return 0;
} Đầu ra
The Given Binary Tree is not a BST The Given Binary Tree is a BST