โปรแกรม C++ ตรวจสอบว่า Binary Tree เป็น BST หรือไม่

Binary Search Tree (BST) เป็นโครงสร้างข้อมูล binary tree ที่มี 3 คุณสมบัติ:

• Left subtree ของโหนดใน BST มีเฉพาะโหนดที่มี key น้อยกว่า key ของโหนดนั้น
• Right subtree ของโหนดใน BST มีเฉพาะโหนดที่มี key มากกว่า key ของโหนดนั้น
• Left และ right subtree ของทุก subtree ต้องเป็น BST ด้วย

อัลกอริทึม

เริ่มต้น
  ฟังก์ชัน BSTUtil()
    ถ้า node เท่ากับ NULL คืนค่า 1
    ถ้าข้อมูลของ node น้อยกว่า min หรือมากกว่า max คืนค่า 0
    ท่อง left และ right sub-trees แบบ recursive
สิ้นสุด

ตัวอย่างโค้ด

#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() {
    // Test case 1: ไม่ใช่ BST
    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;
    
    // Test case 2: เป็น BST
    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;
}

ผลลัพธ์

The Given Binary Tree is not a BST
The Given Binary Tree is a BST