सी ++ में दी गई सीमा में स्थित बीएसटी उपट्री की गणना करें

हमें एक इनपुट के रूप में एक बाइनरी सर्च ट्री दिया जाता है। लक्ष्य बीएसटी में उप-वृक्षों की गिनती का पता लगाना है, जिसमें शुरुआत और अंत की सीमा के बीच नोड मान हैं। यदि प्रारंभ 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 के रूप में होते हैं।

• किसी दिए गए ढांचे के लिए कॉल करके सम्मिलित फ़ंक्शन का उपयोग करके एक बीएसटी बनाएं। रूट नोड (रूट-> राइट =इंसर्ट (70); ) और रूट के बाईं ओर (रूट-> लेफ्ट =इंसर्ट (30); ) में नोड्स को जोड़ने के लिए।

• चर l और h किसी श्रेणी के न्यूनतम और अधिकतम मान को संग्रहीत करने के लिए उपयोग किए जाते हैं।

• परिवर्तनीय गणना पेड़ के अंदर बीएसटी की गिनती को स्टोर करती है जो एल और एच के बीच की सीमा में होती है। प्रारंभ में 0.

• फ़ंक्शन getBtreeCount(Btreenode* root, int Low, int high, int* count) BST की जड़ लेता है, रेंज की बाएँ और दाएँ सीमाओं और काउंट के पते को पैरामीटर के रूप में लेता है और प्रत्येक रिकर्सिव कॉल के लिए गिनती के मान को अपडेट करता है।

• वर्तमान रूट के लिए जाँच करें कि क्या यह NULL है, यदि हाँ तो 1 लौटाएँ क्योंकि यह पेड़ का हिस्सा नहीं है।

• वर्तमान नोड्स के लिए, इसके सभी बाएँ और दाएँ सबट्री नोड की जाँच करें कि क्या वे दी गई सीमा में हैं। पुनरावर्ती कॉल द्वारा getBtreeCount(root->left, Low, High, count); andgetBtreeCount(root->right, Low, High, count);

• यदि दोनों सबट्री रेंज के बीच में हैं और करंट नोड भी रेंज में पड़ा है तो वर्तमान नोड पर रूट किया गया ट्री रेंज में है। वृद्धि की गिनती। अगर (बाएं और दाएं और&रूट->जानकारी>=कम &&रूट->जानकारी <=उच्च) और +**गिनती; वापसी 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