हमें नोड्स से बना एक बाइनरी सर्च ट्री दिया गया है और एक रेंज भी दी गई है और कार्य दिए गए रेंज में स्थित नोड्स की गिनती की गणना करना और परिणाम प्रदर्शित करना है।
बाइनरी सर्च ट्री (BST) एक ऐसा पेड़ है जिसमें सभी नोड नीचे बताए गए गुणों का पालन करते हैं -
-
किसी नोड के बाएँ उपप्रकार की कुंजी उसके पैरेंट नोड की कुंजी से कम या उसके बराबर होती है।
-
नोड के दाएँ उपप्रकार की कुंजी उसके पैरेंट नोड की कुंजी से बड़ी होती है।
इस प्रकार, BST अपने सभी उप-वृक्षों को दो खंडों में विभाजित करता है; लेफ्ट सबट्री और राइट सबट्री और को -
. के रूप में परिभाषित किया जा सकता हैleft_subtree (कुंजी) नोड (कुंजी) ≤ right_subtree (कुंजी)
उदाहरण के लिए
इनपुट -
रेंज:[11, 40]
आउटपुट - गिनती है:5
स्पष्टीकरण -श्रेणी [11, 40] के बीच का नोड मान 14, 19, 27, 31 और 35 है, इसलिए दिए गए बाइनरी सर्च ट्री में कुल 5 नोड हैं।
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
-
डेटा, लेफ्ट पॉइंटर, राइट पॉइंटर वाले नोड की संरचना बनाएं और एक रेंज बनाएं
-
एक नया नोड डालने के लिए एक फ़ंक्शन बनाएं जिसे उपयोगकर्ता दर्ज करेगा।
-
किसी दी गई श्रेणी में स्थित नोड्स की गणना करने के लिए एक अन्य फ़ंक्शन बनाएं।
-
जांचें कि क्या रूट न्यूल है तो वापस लौटें
-
अब, IF रूट की जाँच करें-> डेटा =प्रारंभ और रूट-> डेटा =अंत फिर वापस लौटें 1.
-
अब, IF रूट-> डेटा <=उच्च &&रूट-> डेटा> =कम जांचें, फिर 1 + getCount (रूट-> लेफ्ट, एंड, स्टार्ट) + रिकर्सिवली_कॉल_काउंट_फंक्शन (रूट-> राइट, एंड, स्टार्ट)
लौटाएं। -
और अगर, रूट-> डेटा <एंड फिर रिकर्सिवली_कॉल_काउंट_फंक्शन (रूट-> राइट, एंड, स्टार्ट) पर लौटें
-
अन्यथा, रिकर्सिवली_कॉल_काउंट_फंक्शन (रूट-> लेफ्ट, एंड, स्टार्ट) पर लौटें
उदाहरण
#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