यह जांचने के लिए एक प्रोग्राम है कि बाइनरी ट्री बीएसटी है या नहीं सी में?

बाइनरी ट्री एक ट्री डेटा संरचना है जिसमें प्रत्येक नोड के लिए दो चाइल्ड नोड होते हैं। चाइल्ड नोड्स के दो होने को बाएँ और दाएँ बच्चे के रूप में संदर्भित किया जाता है।

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 () विधि का उपयोग करके।