تصور کنید که یک درخت باینری به شما داده شده است و از شما خواسته شده است که ببینید که این درخت یک درخت جستجوی باینری یا همون BST هست یا خیر.یک BST یک ساختمان داده درخت باینری است که قابلیت‌های زیر را دارد.
مورد آخر به این معنی است که هر نودی را که شما در نظر بگیرید از ۲ قاعده اول تبعیت می کنند. با توجه به مواردی که گفته شد یک BST هیچ‌وقت عضو تکراری ندارد. در شکل زیر یک BST را می بینید.
در این مطلب می‌خواهیم مسأله گفته شده را حل کنیم یعنی یک درخت باینری داریم و می‌خواهیم مشخص کنیم که این درخت BST است یا خیر.ایده این کار به این صورت است که به صورت inorder درخت را پیمایش می‌کنیم و هر بار مقدار نود قبلی را نگهداری می کنیم. به خاطر اینکه پیمایش inorder یک BST باعث به وجود آمدن یک آرایه مرتب می‌شود پس در هر بار پیمایش باید مقدار قبلی ازمقدار کنونی کمتر باشد. در غیر این صورت درخت BST نیست. کد c++ این برنامه در ادامه آورده شده است.
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has data, pointer to
left child and a pointer to right child */
struct Node {
int data;
struct Node *left, *right;
Node(int data)
{
this->data = data;
left = right = NULL;
}
};
// Utility function to check if Binary Tree is BST
bool isBSTUtil(struct Node* root, int& prev)
{
// traverse the tree in inorder fashion and
// keep track of prev node
if (root) {
if (!isBSTUtil(root->left, prev))
return false;
// Allows only distinct valued nodes
if (root->data <= prev)
return false;
// Initialize prev to current
prev = root->data;
return isBSTUtil(root->right, prev);
}
return true;
}
// Function to check if Binary Tree is BST
bool isBST(Node* root)
{
int prev = INT_MIN;
return isBSTUtil(root, prev);
}
/* Driver program to test above functions*/
int main()
{
struct Node* root = new Node(5);
root->left = new Node(2);
root->right = new Node(15);
root->left->left = new Node(1);
root->left->right = new Node(4);
if (isBST(root))
cout << "Is BST";
else
cout << "Not a BST";
return 0;
}
دقت کنید که در کد بالا همانطور که BST را به صورت بازگشتی تعریف کردیم تابع isBSTUtil نیز به صورت بازگشتی تعریف شده است تا بتواند پیمایش inorder را به راحتی انجام دهد. همچنین برای بار اول مقدار prev برابر با کوچکترین عدد int قرار داده شده است.با وب سایت tosinso همراه باشید.