আমাদের ইনপুট হিসাবে একটি বাইনারি ট্রি দেওয়া হয়েছে৷ লক্ষ্য হল এর ভিতরে সাবট্রি হিসাবে উপস্থিত বাইনারি সার্চ ট্রি (BSTs) এর সংখ্যা খুঁজে বের করা। BST হল একটি বাইনারি ট্রি যার বাম বাচ্চা মূলের চেয়ে কম এবং ডানের বাচ্চা মূলের চেয়ে বেশি।
উদাহরণস্বরূপ
ইনপুট
মান ইনপুট করার পরে যে গাছটি তৈরি হবে তা নীচে দেওয়া হল -
আউটপুট
Count the Number of Binary Search Trees present in a Binary Tree are: 2
ব্যাখ্যা
আমাদেরকে পূর্ণসংখ্যার মানগুলির একটি অ্যারে দেওয়া হয়েছে যা একটি বাইনারি ট্রি তৈরি করতে ব্যবহৃত হয় এবং আমরা এটিতে একটি বাইনারি অনুসন্ধান গাছ আছে কিনা তা পরীক্ষা করব। প্রতিটি রুট নোড বাইনারি সার্চ ট্রিকে প্রতিনিধিত্ব করে তাই প্রদত্ত বাইনারি ট্রিতে আমরা দেখতে পাচ্ছি যে অন্য কোন বাইনারি সার্চ ট্রি নেই তাই গণনা হল 2 যা একটি বাইনারি গাছের মোট লিফ নোডের সংখ্যা৷
ইনপুট
মান ইনপুট করার পরে যে গাছটি তৈরি হবে তা নীচে দেওয়া হল -
আউটপুট
Count the Number of Binary Search Trees present in a Binary Tree are: 6
ব্যাখ্যা
আমাদেরকে পূর্ণসংখ্যার মানের একটি অ্যারে দেওয়া হয়েছে যা একটি বাইনারিট্রি তৈরি করতে ব্যবহৃত হয় এবং আমরা এটিতে একটি বাইনারি সার্চ ট্রি আছে কিনা তা পরীক্ষা করব। প্রতিটি রুটনোড বাইনারি সার্চ ট্রিকে প্রতিনিধিত্ব করে তাই প্রদত্ত বাইনারি ট্রিতে আমরা দেখতে পাচ্ছি যে 4টি লিফ নোড এবং দুটি সাবট্রি রয়েছে যা BST গঠন করছে তাই গণনা হল 6৷
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি হল -
এই পদ্ধতিতে আমরা নোড N এর বাম সাবট্রিতে নোডের সবচেয়ে বড় মানটি খুঁজে পাব এবং এটি N-এর থেকে কম কিনা তা পরীক্ষা করব। এছাড়াও, আমরা নোড N-এর ডান সাবট্রিতে সবচেয়ে ছোট মানটি খুঁজে পাব এবং এটির চেয়ে বেশি কিনা তা পরীক্ষা করব। N. যদি সত্য হয়, তাহলে এটি একটি BST৷ নীচের দিকে বাইনারি ট্রিটি অতিক্রম করুন এবং উপরের শর্তগুলি এবং BSTগুলির বৃদ্ধির সংখ্যা পরীক্ষা করুন
-
প্রতিটি নোড_ডেটার নোডে বিএসটি-প্রেজেন্টের সংখ্যা, সেই গাছের সর্বোচ্চ মান, ন্যূনতম মান, বুলিয়ান ট্রু যদি সেই সাবট্রিটি একটি BST হয় তার মতো তথ্য থাকে।
-
ফাংশন BST_present(struct tree_node* parent) প্যারেন্ট এ রুট করা বাইনারি ট্রির ভিতরে উপস্থিত BST এর গণনা খুঁজে পায়।
-
যদি অভিভাবকটি NULL হয় তাহলে {0, min, max, true } দিন যেখানে min হল INT-MIN এবং সর্বোচ্চ হল INT_MAX৷
-
যদি বাম এবং ডান সন্তান শূন্য হয় তাহলে { 1, পিতামাতা−>ডেটা, পিতামাতা−>ডেটা, সত্য }
ফেরত দিন। -
নোড_ডেটা লেফট সেট করুন =BST_present(parent−>left); এবং node_data Right =BST_present(parent−>right);
-
নোড n1 নিন এবং n1.lowest =min(parent−>data, (min(Left.lowest,Right.lowest))) এর ডান সাবট্রিতে সর্বনিম্ন হিসাবে সেট করুন।
-
n1.highest =max(parent−>data, (max(Left.highest, Right.highest))) সেট করুন; এর বাম সাবট্রিতে সর্বোচ্চ।
-
যদি(Left.check &&Right.check &&parent−>data> Left.highest &&parent−>data
-
n1.total_bst =1 + Left.total_bst + Right.total_bst;
হিসাবে bsts সংখ্যা বাড়ান -
অন্যথায় n1.check =মিথ্যা সেট করুন এবং n1.total_bst =Left.total_bst +Right.total_bst হিসাবে গণনা করুন।
-
শেষে n1 ফেরত দিন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
struct tree_node{
struct tree_node* left;
struct tree_node* right;
int data;
tree_node(int data){
this−>data = data;
this−>left = NULL;
this−>right = NULL;
}
};
struct node_data{
int total_bst;
int highest, lowest;
bool check;
};
node_data BST_present(struct tree_node* parent){
if(parent == NULL){
int max = INT_MAX;
int min = INT_MIN;
return { 0, min, max, true };
}
if(parent−>left == NULL){
if(parent−>right == NULL){
return { 1, parent−>data, parent−>data, true };
}
}
node_data Left = BST_present(parent−>left);
node_data Right = BST_present(parent−>right);
node_data n1;
n1.lowest = min(parent−>data, (min(Left.lowest, Right.lowest)));
n1.highest = max(parent−>data, (max(Left.highest, Right.highest)));
if(Left.check && Right.check && parent−>data > Left.highest && parent−>data < Right.lowest){
n1.check = true;
n1.total_bst = 1 + Left.total_bst + Right.total_bst;
} else{
n1.check = false;
n1.total_bst = Left.total_bst + Right.total_bst;
}
return n1;
}
int main(){
struct tree_node* root = new tree_node(3);
root−>left = new tree_node(7);
root−>right = new tree_node(4);
root−>left−>left = new tree_node(5);
root−>right−>right = new tree_node(1);
root−>left−>left−>left = new tree_node(10);
cout<<"Count the Number of Binary Search Trees present in a Binary Tree are: "<<BST_present(root).total_bst;
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −
উৎপন্ন করবেCount the Number of Binary Search Trees present in a Binary Tree are: 2
