এই টিউটোরিয়ালে, আমরা একটি প্রদত্ত বাইনারি গাছের উপরের দৃশ্যে প্রদর্শিত সমস্ত নোডগুলিকে প্রিন্ট করার জন্য একটি প্রোগ্রাম নিয়ে আলোচনা করব৷
একটি নির্দিষ্ট বাইনারি গাছের জন্য, একটি নোড তার উপরের দৃশ্যে উপস্থিত হয় যদি এটি তার অনুভূমিক দূরত্বে প্রথম নোড হয়। একটি নোড 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
