আমাদেরকে নোড দিয়ে তৈরি একটি বাইনারি সার্চ ট্রি দেওয়া হয়েছে এবং একটি পরিসরও দেওয়া হয়েছে এবং কাজটি হল প্রদত্ত রেঞ্জে থাকা নোডগুলির গণনা করা এবং ফলাফল প্রদর্শন করা৷
একটি বাইনারি সার্চ ট্রি (বিএসটি) হল একটি গাছ যেখানে সমস্ত নোড নীচের উল্লেখিত বৈশিষ্ট্যগুলি অনুসরণ করে -
-
একটি নোডের বাম সাবট্রিতে মূল নোডের কী থেকে কম বা সমান একটি কী থাকে৷
-
একটি নোডের ডান সাবট্রিতে মূল নোডের কী থেকে বড় একটি কী থাকে৷
এইভাবে, BST তার সমস্ত উপ-বৃক্ষকে দুটি ভাগে ভাগ করে; বাম সাবট্রি এবং ডান সাবট্রি এবং −
হিসাবে সংজ্ঞায়িত করা যেতে পারেleft_subtree (কী) ≤ নোড (কী) ≤ right_subtree (কী)
উদাহরণস্বরূপ
ইনপুট −
পরিসর:[১১, ৪০]
আউটপুট - গণনা হল:5
ব্যাখ্যা − রেঞ্জ [11, 40] এর মধ্যে নোডের মান হল 14, 19, 27, 31 এবং 35 তাই একটি প্রদত্ত বাইনারি সার্চ ট্রিতে মোট 5টি নোড রয়েছে৷
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
ডেটা, বাম পয়েন্টার, ডান পয়েন্টার সহ একটি নোডের একটি কাঠামো তৈরি করুন এবং একটি পরিসর তৈরি করুন
-
একটি নতুন নোড সন্নিবেশ করার জন্য একটি ফাংশন তৈরি করুন যা ব্যবহারকারী প্রবেশ করবে৷
৷ -
একটি নির্দিষ্ট পরিসরে থাকা নোডগুলি গণনা করার জন্য অন্য একটি ফাংশন তৈরি করুন৷
-
রুটটি NULL হলে চেক করুন তারপর ফিরে আসুন
-
এখন, IF root->data=Start AND root->data=End চেক করুন তারপর 1 রিটার্ন করুন।
-
এখন, IF root->data <=high &&root->data>=low চেক করুন তারপর 1 + getCount(root->left, End, Start) + recursively_call_count_function(root->ডান, শেষ, শুরু)
-
অন্যথায় যদি, root->ডেটা
ডান, শেষ, শুরু) -
অন্যথায়, recursively_call_count_function(root->বাম, শেষ, শুরু)
ফিরে আসুন
উদাহরণ
#include<iostream>
using namespace std;
// A BST node
struct node{
int data;
struct node* left, *right;
};
// Utility function to create new node
node *newNode(int data){
node *temp = new node;
temp->data = data;
temp->left = temp->right = NULL;
return (temp);
}
int findcount(node *root, int low, int high){
// Base case
if (!root){
return 0;
}
if (root->data == high && root->data == low){
return 1;
}
// If current node is in range, then include it in count and
// recur for left and right children of it
if (root->data <= high && root->data >= low){
return 1 + findcount(root->left, low, high) +
findcount(root->right, low, high);
}
else if (root->data < low){
return findcount(root->right, low, high);
}
// Else recur for left child
else{
return findcount(root->left, low, high);
}
}
// main function
int main(){
// Let us construct the BST shown in the above figure
node *root = newNode(27);
root->left = newNode(14);
root->right = newNode(35);
root->left->left = newNode(10);
root->left->right = newNode(19);
root->right->left = newNode(31);
root->right->right = newNode(42);
int low = 10;
int high = 50;
cout << "Count of nodes between [" << low << ", " << high
<< "] is " << findcount(root, low, high);
return 0;
} আউটপুট
আমরা উপরের কোডটি চালালে আমরা নিম্নলিখিত আউটপুট পাব −
Count of nodes between [10, 50] is 7
