इस ट्यूटोरियल में, हम एक दिए गए बाइनरी ट्री के टॉप व्यू में दिखाई देने वाले सभी नोड्स को प्रिंट करने के प्रोग्राम पर चर्चा करेंगे।
किसी विशेष बाइनरी ट्री के लिए, एक नोड उसके टॉप व्यू में दिखाई देता है यदि वह अपने क्षैतिज दूरी (horizontal distance) पर सबसे पहला नोड है। नोड x के बाएं नोड की क्षैतिज दूरी x-1 और दाएं नोड की x+1 होती है।
इसे हल करने के लिए, हम लेवल ऑर्डर ट्रैवर्सल करेंगे ताकि किसी विशेष लेवल के लिए सबसे ऊपर का नोड अन्य नोड्स से पहले मिल जाए। साथ ही, हैशिंग का उपयोग करके जांचेंगे कि चयनित नोड टॉप व्यू में दिखाई देता है या नहीं।
C++ उदाहरण
#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