ต้นไม้ไบนารีเป็นโครงสร้างข้อมูลต้นไม้ซึ่งมีโหนดย่อยสองโหนดสำหรับแต่ละโหนด โหนดย่อยที่มีสองเรียกว่าลูกซ้ายและขวา
BST คือโครงสร้างแบบทรีที่ทรีย่อยด้านซ้ายมีโหนดที่มีค่าน้อยกว่ารูท และทรีย่อยทางขวามีโหนดที่มีค่ามากกว่ารูทนั้น
ที่นี่ เราจะตรวจสอบว่าไบนารีทรีเป็น BST หรือไม่ -
ในการตรวจสอบสิ่งนี้ เราต้องตรวจสอบเงื่อนไข BST บนไบนารีทรี สำหรับการตรวจสอบโหนดรูทสำหรับโหนดย่อยด้านซ้ายควรน้อยกว่ารูทนั้น ลูกที่ถูกต้องควรมีค่ามากกว่ารูทนั้นสำหรับโหนดทั้งหมดของทรีที่มีรายการย่อยอยู่
โปรแกรมตรวจสอบว่าต้นไม้ไบนารีเป็น 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;
} ผลลัพธ์
The given tree is a BST
อธิบายโค้ด
รหัสด้านบนตรวจสอบ BST เมธอดหลัก สร้างแผนผังและเรียกเมธอด isBST() เมธอดนี้จะตรวจสอบว่าลูกซ้ายและขวาทำตามกฎ BST หรือไม่ และทรีย่อยที่สร้างขึ้นนั้นเป็นของ BST เช่นกันโดยใช้เมธอด isBSTuntil()
