इस ट्यूटोरियल में, हम किसी दिए गए बाइनरी ट्री के शीर्ष दृश्य में दिखाई देने वाले सभी नोड्स को प्रिंट करने के लिए एक प्रोग्राम पर चर्चा करेंगे।
किसी विशेष बाइनरी ट्री के लिए, एक नोड अपने शीर्ष दृश्य में प्रकट होता है यदि यह अपनी क्षैतिज दूरी पर सबसे पहला नोड है। नोड x के बाएं नोड के लिए क्षैतिज दूरी x-1 है और नोड x के दाएं नोड के लिए x+1 है।
इसे हल करने के लिए, हम लेवल ऑर्डर ट्रैवर्सल करेंगे ताकि हम उस स्तर पर मौजूद अन्य नोड्स से पहले किसी विशेष स्तर के लिए सबसे ऊपरी नोड प्राप्त कर सकें। इसके अलावा, हम हैशिंग का उपयोग यह जांचने के लिए करेंगे कि चयनित नोड शीर्ष दृश्य में दिखाई दे रहा है या नहीं।
उदाहरण
#include <iostream>
#include<queue>
#include<map>
using namespace std;
struct Node{
Node * left;
Node* right;
int h_dist;
int data;
};
Node* create_node(int key){
Node* node=new Node();
node->left = node->right = NULL;
node->data=key;
return node;
}
void print_topview(Node* root){
if(root==NULL)
return;
queue<Node*>q;
map<int,int> m;
int h_dist=0;
root->h_dist=h_dist;
q.push(root);
cout<< "Top View for the given tree:" << endl;
while(q.size()){
h_dist=root->h_dist;
if(m.count(h_dist)==0)
m[h_dist]=root->data;
if(root->left){
root->left->h_dist=h_dist-1;
q.push(root->left);
}
if(root->right){
root->right->h_dist=h_dist+1;
q.push(root->right);
}
q.pop();
root=q.front();
}
for(auto i=m.begin();i!=m.end();i++){
cout<<i->second<< " ";
}
}
int main(){
Node* root = create_node(11);
root->left = create_node(23);
root->right = create_node(35);
root->left->right = create_node(47);
root->left->right->right = create_node(59);
root->left->right->right->right = create_node(68);
print_topview(root);
return 0;
} आउटपुट
Top View for the given tree: 23 11 35 68