ইনপুট হিসাবে আমাদের একটি বাইনারি অনুসন্ধান গাছ দেওয়া হয়েছে। লক্ষ্য হল BST-তে উপবৃক্ষের গণনা খুঁজে বের করা যার সূচনা এবং শেষের সীমার মধ্যে নোডের মান রয়েছে। যদি শুরু হয় 5 এবং শেষ হয় 50। তাহলে BST-তে সাবট্রি গণনা করুন যার সমস্ত নোডের ওজন আছে>=5 এবং <=50।
ইনপুট − বৃক্ষ নীচে দেওয়া হল − পরিসর [ 3-6 ]
আউটপুট − পরিসরে পড়ে থাকা গাছের সংখ্যা − 2
ব্যাখ্যা − শুধুমাত্র নোড 4 এবং 6 এর জন্য। তাদের উপবৃক্ষ ( NULL ) 3-6 এর মধ্যে থাকে।
ইনপুট − গাছ নীচে দেওয়া হয়েছে:পরিসর [ 12-20 ]
আউটপুট − 3
পরিসরে পড়ে থাকা গাছের সংখ্যাব্যাখ্যা − নোড 16, 14 এবং 20 এর জন্য। তাদের সাবট্রি 12-20 এর মধ্যে থাকে।
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
স্ট্রাকচার Btreenode একটি গাছের একটি নোড তৈরি করতে ব্যবহৃত হয়, যেখানে তথ্য অংশটি পূর্ণসংখ্যা হিসাবে এবং স্ব-রেফারেন্সিং বাম এবং ডান পয়েন্টারগুলি সাবট্রিকে নির্দেশ করতে ব্যবহৃত হয়।
-
ফাংশন Btreenode* insert(int data) তথ্য হিসাবে ডেটা এবং NULL হিসাবে বাম এবং ডান পয়েন্টার সহ একটি নোড তৈরি করতে ব্যবহৃত হয়।
-
একটি প্রদত্ত কাঠামোর জন্য কল করে সন্নিবেশ ফাংশন ব্যবহার করে একটি BST তৈরি করুন। রুট নোডে অভ্যন্তরীণভাবে নোড যোগ করতে ( root->right =insert(70); ) এবং রুটের বাম দিকে ( root->left =insert(30); ).
-
ভেরিয়েবল l এবং h একটি পরিসরের সর্বনিম্ন এবং সর্বোচ্চ মান সংরক্ষণ করতে ব্যবহৃত হয়।
-
ভেরিয়েবল কাউন্ট l এবংh এর মধ্যে থাকা গাছের ভিতরে BST এর গণনা সঞ্চয় করে। প্রাথমিকভাবে 0.
-
ফাংশন getBtreeCount(Btreenode* root, int low, int high, int* count) BST এর রুট নেয়, পরিসীমার বাম ও ডান সীমানা এবং পরামিতি হিসাবে গণনার ঠিকানা এবং প্রতিটি পুনরাবৃত্ত কলের জন্য গণনার মান আপডেট করে।
-
বর্তমান রুটের জন্য এটি NULL কিনা তা পরীক্ষা করুন, যদি হ্যাঁ 1 দিন কারণ এটি গাছের অংশ নয়৷
-
বর্তমান নোডগুলির জন্য, এর সমস্ত বাম এবং ডান সাবট্রি নোডগুলি প্রদত্ত পরিসরে রয়েছে কিনা তা পরীক্ষা করুন। রিকার্সিভ কল দ্বারা getBtreeCount(root->left, low, high, count); andgetBtreeCount(root->ডান, কম, উচ্চ, গণনা);
-
যদি উভয় সাবট্রি রেঞ্জের মধ্যে পড়ে থাকে এবং বর্তমান নোডটিও রেঞ্জে পড়ে থাকে তাহলে বর্তমান নোডে থাকা গাছটি রেঞ্জের মধ্যে থাকে। বৃদ্ধির সংখ্যা। যদি (বাম &&ডান &&রুট->তথ্য>=কম &&রুট->তথ্য <=উচ্চ) এবং ++*গণনা; রিটার্ন 1.
-
শেষে গণনা সব উপবৃক্ষের গণনা হিসাবে আপডেট মান থাকবে।
- গণনায় ফলাফল প্রিন্ট করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
// A BST node
struct Btreenode {
int info;
Btreenode *left, *right;
};
int getBtreeCount(Btreenode* root, int low, int high, int* count){
// Base case
if (root == NULL)
return 1;
int left = getBtreeCount(root->left, low, high, count);
int right = getBtreeCount(root->right, low, high, count);
if (left && right && root->info >= low && root->info <= high) {
++*count;
return 1;
}
return 0;
}
Btreenode* insert(int data){
Btreenode* temp = new Btreenode;
temp->info = data;
temp->left = temp->right = NULL;
return (temp);
}
int main(){
/* BST for input
50
/ \
30 70
/ \ / \
20 40 60 80 */
Btreenode* root = insert(50);
root->left = insert(30);
root->right = insert(70);
root->left->left = insert(20);
root->left->right= insert(40);
root->right->left = insert(60);
root->right->right = insert(80);
int l = 10;
int h = 50;
int count=0;
getBtreeCount(root, l, h, &count);
cout << "Count of subtrees lying in range: " <<count;
return 0;
} আউটপুট
Count of subtrees lying in range: 3
