इस समस्या में, हमें एक बाइनरी ट्री और ट्री में दो लेवल (ऊपरी और निचले) दिए जाते हैं और हमें ट्री के ऊपरी और निचले स्तरों के बीच सभी नोड्स को प्रिंट करना होता है।
बाइनरी ट्री एक विशेष पेड़ है जिसके प्रत्येक नोड में अधिकतम दो नोड (एक/दो/कोई नहीं) होते हैं।
आइए समस्या को समझने के लिए एक उदाहरण लेते हैं -
ऊपरी - 1
निचला -3
आउटपुट -
6 3 9 7 4 8 10
इस समस्या को हल करने के लिए, हमें पेड़ के नोड्स को एक निश्चित स्तर पर प्रिंट करना होगा। हम ऊपरी . से लूप का उपयोग करके एक पुनरावर्ती फ़ंक्शन को कॉल करेंगे करने के लिए निचला पेड़ में स्तर।
यह एल्गोरिथम सरल है लेकिन क्रम n 2 . का अधिक जटिल है ।
एक अधिक प्रभावी समाधान इनऑर्डर ट्रैवर्सल कर रहा है और एक कतार का उपयोग कर रहा है। और दिए गए ऊपरी और निचले स्तरों के भीतर नोड्स प्रिंट करें।
हमारे समाधान को लागू करने का कार्यक्रम -
उदाहरण
#include <iostream>
#include <queue>
using namespace std;
struct Node{
int key;
struct Node* left, *right;
};
void printNodesAtLevel(Node* root, int low, int high){
queue <Node *> Q;
Node *marker = new Node;
int level = 1;
Q.push(root);
Q.push(marker);
while (Q.empty() == false){
Node *n = Q.front();
Q.pop();
if (n == marker){
cout << endl;
level++;
if (Q.empty() == true || level > high) break;
Q.push(marker);
continue;
}
if (level >= low)
cout<<n->key<<" ";
if (n->left != NULL) Q.push(n->left);
if (n->right != NULL) Q.push(n->right);
}
}
Node* insertNode(int key){
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
int main() {
struct Node *root = insertNode(6);
root->left = insertNode(3);
root->right = insertNode(9);
root->left->left = insertNode(7);
root->left->right = insertNode(4);
root->left->right->left = insertNode(8);
root->left->right->right = insertNode(10);
root->left->right->right->left = insertNode(5);
root->left->right->right->right = insertNode(1);
root->left->right->left->left = insertNode(14);
root->left->right->left->right = insertNode(26);
int upper = 3;
int lower = 1;
cout << "Level wise Nodes between level "<<lower<<" and "<<upper<<" are \n";
printNodesAtLevel(root, lower, upper);
return 0;
} आउटपुट
Level wise Nodes between level 1 and 3 are 6 3 9 7 4