हमें इनपुट के रूप में एक बाइनरी सर्च ट्री दिया गया है। लक्ष्य 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 रेंज के न्यूनतम और अधिकतम मान संग्रहीत करने के लिए उपयोग किए जाते हैं।
- चर count ट्री के अंदर उन BST की गणना संग्रहीत करता है जो l और h के बीच रेंज में हैं। प्रारंभ में 0।
- फ़ंक्शन getBtreeCount(Btreenode* root, int low, int high, int* count) BST के रूट, रेंज की बाएं और दाएं सीमाओं और count के पते को पैरामीटर के रूप में लेता है और प्रत्येक रिकर्सिव कॉल के लिए count के मान को अपडेट करता है।
- वर्तमान रूट के लिए जांचें कि क्या यह NULL है, यदि हाँ तो 1 लौटाएं क्योंकि यह ट्री का हिस्सा नहीं है।
- वर्तमान नोड्स के लिए, रिकर्सिव कॉल द्वारा इसके सभी बाएं और दाएं उपट्री नोड्स की जांच करें कि क्या वे दी गई रेंज में हैं। getBtreeCount(root->left, low, high, count); और getBtreeCount(root->right, low, high, count);
- यदि दोनों उपट्री रेंज के बीच में हैं और वर्तमान नोड भी रेंज में है तो वर्तमान नोड पर रूटेड ट्री रेंज में है। count बढ़ाएं। if (left && right && root->info >= low && root->info <= high) और ++*count; return 1.
- अंत में count में सभी उपट्री की गणना के रूप में अपडेटेड मान होगा।
- count में परिणाम प्रिंट करें।
उदाहरण कोड
#include <bits/stdc++.h> using namespace std; // एक BST नोड struct Btreenode { int info; Btreenode *left, *right; }; int getBtreeCount(Btreenode* root, int low, int high, int* count){ // बेस केस 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 इनपुट के लिए 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; return 0; } आउटपुट
रेंज में आने वाले उपट्री की संख्या: 3
