একটি বাইনারি গাছ বিএসটি কিনা তা পরীক্ষা করার জন্য একটি প্রোগ্রাম সি তে?

একটি বাইনারি ট্রি হল একটি ট্রি ডেটা স্ট্রাকচার যাতে প্রতিটি নোডের জন্য দুটি চাইল্ড নোড থাকে। চাইল্ড নোড দুটিকে বাম এবং ডান শিশু হিসাবে উল্লেখ করা হয়।

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() পদ্ধতিতে কল করে। এই পদ্ধতিটি পরীক্ষা করে যে বাম এবং ডান শিশু বিএসটি নিয়ম অনুসরণ করে কিনা তাও isBSTuntil() পদ্ধতি ব্যবহার করে গঠিত সাবট্রিগুলিও BST-এর।