এই টিউটোরিয়ালে, আমরা একটি প্রদত্ত বাইনারি ট্রির টপ ভিউতে প্রদর্শিত সমস্ত নোড প্রিন্ট করার একটি প্রোগ্রাম নিয়ে আলোচনা করব।
টপ ভিউ কী?
একটি নির্দিষ্ট বাইনারি ট্রির জন্য, একটি নোড তার টপ ভিউতে প্রদর্শিত হয় যদি সেটি তার আঙুলের দূরত্বে (horizontal distance) থাকা সবচেয়ে প্রথম নোড হয়। একটি নোড x-এর বাম নোডের আঙুলের দূরত্ব হল x-1 এবং ডান নোডের আঙুলের দূরত্ব হল x+1।
সমাধানের পদ্ধতি
এই সমস্যাটি সমাধান করার জন্য আমরা লেভেল অর্ডার ট্রাভার্সাল (level order traversal) করব যাতে একটি নির্দিষ্ট লেভেলের টপমোস্ট নোডটি অন্যান্য নোডের আগে পাওয়া যায়। আরও, আমরা হ্যাশিং (hashing) ব্যবহার করব যাতে বুঝতে পারি নির্বাচিত নোডটি টপ ভিউতে দৃশ্যমান কিনা।
উদাহরণ কোড
#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
