हमें नोड्स से बना एक बाइनरी सर्च ट्री दिया गया है और एक रेंज भी दी गई है और कार्य उन नोड्स की संख्या की गणना करना है जो दी गई रेंज में हैं और परिणाम प्रदर्शित करना है।
एक बाइनरी सर्च ट्री (BST) एक ट्री है जिसमें सभी नोड्स नीचे उल्लिखित गुणों का पालन करते हैं:
- एक नोड का बायां सबट्री उस नोड की कुंजी से कम या बराबर कुंजी रखता है।
- एक नोड का दायां सबट्री उस नोड की कुंजी से अधिक कुंजी रखता है।
इस प्रकार, BST अपने सभी सब-ट्री को दो खंडों में विभाजित करता है; बायां सबट्री और दायां सबट्री और इसे इस प्रकार परिभाषित किया जा सकता है:
left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)
उदाहरण
इनपुट: BST की छवि, रेंज: [11, 40]
आउटपुट: count is: 5
व्याख्या: रेंज [11, 40] के बीच नोड मान 14, 19, 27, 31 और 35 हैं इसलिए दिए गए बाइनरी सर्च ट्री में कुल 5 नोड्स हैं।
उपयोग किया गया दृष्टिकोण:
- डेटा, लेफ्ट पॉइंटर, राइट पॉइंटर वाला नोड का स्ट्रक्चर बनाएं और एक रेंज बनाएं
- एक फ़ंक्शन बनाएं जो यूजर द्वारा दर्ज नए नोड को डालेगा
- दी गई रेंज में आने वाले नोड्स गिनने के लिए एक और फ़ंक्शन बनाएं
- जांचें यदि रूट NULL है तो वापस लौटें
- अब, जांचें यदि रूट->डेटा == स्टार्ट && रूट->डेटा == एंड तो 1 वापस करें
- अब, जांचें यदि रूट->डेटा <= हाई && रूट->डेटा >= लो तो 1 + getCount(रूट->लेफ्ट, एंड, स्टार्ट) + रिकर्सिवली_कॉल_काउंट_फंक्शन(रूट->राइट, एंड, स्टार्ट) वापस करें
- अन्यथा यदि, रूट->डेटा < एंड तो रिकर्सिवली_कॉल_काउंट_फंक्शन(रूट->राइट, एंड, स्टार्ट) वापस करें
- अन्यथा, रिकर्सिवली_कॉल_काउंट_फंक्शन(रूट->लेफ्ट, एंड, स्टार्ट) वापस करें
उदाहरण (C++ कोड)
#include<iostream>
using namespace std;
// एक BST नोड
struct node{
int data;
struct node* left, *right;
};
// नया नोड बनाने के लिए यूटिलिटी फ़ंक्शन
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){
// बेस केस
if (!root){
return 0;
}
if (root->data == high && root->data == low){
return 1;
}
// यदि वर्तमान नोड रेंज में है, तो इसे काउंट में शामिल करें और
// इसके बाएं और दाएं बच्चों के लिए पुनरावृत्ति करें
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{
return findcount(root->left, low, high);
}
}
// मुख्य फ़ंक्शन
int main(){
// आइए उपरोक्त आकृति में दिखाए गए BST का निर्माण करें
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
