Chương trình C++ kiểm tra cây cho trước có phải cây tìm kiếm nhị phân (BST)

Cây tìm kiếm nhị phân (Binary Search Tree - BST) là cấu trúc dữ liệu cây nhị phân có 3 tính chất:

• Cây con trái của một nút chỉ chứa các nút với khóa nhỏ hơn khóa của nút.
• Cây con phải của một nút chỉ chứa các nút với khóa lớn hơn khóa của nút.
• Cây con trái và phải của mỗi cây con cũng phải là BST.

Thuật toán

Bắt đầu
  Hàm BSTUtil()
    Nếu node == NULL trả về 1.
    Nếu dữ liệu node < min hoặc > max trả về 0.
    Duyệt đệ quy cây con trái và phải.
Kết thúc.

Mã ví dụ

#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 << "Cây cho là BST" << endl;
    else
        cout << "Cây cho không phải 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 << "Cây cho là BST" << endl;
    else
        cout << "Cây cho không phải BST" << endl;
    return 0;
}

Kết quả

Cây cho không phải BST
Cây cho là BST