इस समस्या में, हमें बाइनरी सर्च ट्री के दो नोड्स दिए गए हैं। और हमें ट्री में होने वाली k1 से k2 की रेंज में सभी मानों को प्रिंट करना है। यानी हमें उन सभी मानों को प्रिंट करना है जो k1 से बड़े और k2 से छोटे हैं। और हमें इन सभी कुंजियों को उनके मानों के बढ़ते क्रम में प्रिंट करना है।
बाइनरी सर्च ट्री एक ट्री है जो इन 3 गुणों का पालन करता है -
बाएं सबट्री में नोड्स के मान नोड के मान से कम होते हैं।
दाएं सबट्री में नोड्स के मान नोड के मान से बड़े होते हैं।
एक सबट्री भी बाइनरी सर्च ट्री होनी चाहिए। ट्री में डुप्लिकेट नोड्स की अनुमति नहीं है।
उदाहरण,
आइए एक उदाहरण लेकर इस विषय को बेहतर ढंग से समझते हैं,
Input : k1 = 12 and k2 = 25. Output : 15, 20, 24
ट्री -
व्याख्या - ट्री को ट्रैवर्स करने पर, सभी तत्वों को ट्रैवर्स किया जाएगा और वे तत्व जो रेंज 12 से 25 के बीच हैं यानी एक नोड x के लिए, 12 ≤ x ≥ 25 प्रिंट होंगे।
यहां, हम इस समस्या को हल करने के लिए BST के गुणों का उपयोग करेंगे। यानी बाएं सबट्री के सभी तत्व रूट से छोटे हैं और दाएं सबट्री के सभी तत्व रूट नोड से बड़े हैं। और हम इस समस्या को हल करने के लिए BST के इनऑर्डर ट्रैवर्सल का उपयोग करेंगे। अब, आइए इस समस्या को हल करने के लिए एक एल्गोरिदम बनाते हैं।
एल्गोरिदम
चरण 1 : रूट नोड की तुलना k1 और k2 से करें। चरण 2 : यदि रूट k1 से बड़ा है। बाएं सबट्री को पुनरावर्ती रूप से खोजने के लिए कॉल करें। चरण 3 : यदि रूट k2 से छोटा है। दाएं सबट्री को पुनरावर्ती रूप से खोजने के लिए कॉल करें। चरण 4 : यदि ट्री का रूट रेंज में है। तो रूट के मान को प्रिंट करें।
उदाहरण
अब, इस एल्गोरिदम के आधार पर, आइए इस समस्या को हल करने के लिए एक प्रोग्राम बनाते हैं।
#include<bits/stdc++.h> using namespace std; class node{ public: int data; node *left; node *right; }; void nodesInRange(node *root, int k1, int k2){ if ( NULL == root ) return; if ( k1 < root->data ) nodesInRange(root->left, k1, k2); if ( k1 <= root->data && k2 >= root->data ) cout<<root->data<<"\t"; if ( k2 > root->data ) nodesInRange(root->right, k1, k2); } node* insert(int data){ node *temp = new node(); temp->data = data; temp->left = NULL; temp->right = NULL; return temp; } int main(){ node *root = new node(); int k1 = 12, k2 = 25; root = insert(20); root->left = insert(10); root->right = insert(24); root->left->left = insert(8); root->left->right = insert(15); root->right->right = insert(32); cout<<"The values of node within the range are\t"; nodesInRange(root, k1, k2); return 0; } आउटपुट
The values of node within the range are 15 20 24.
