Trong hướng dẫn này, chúng ta sẽ thảo luận về chương trình in tất cả các nút xuất hiện trong top view (hàng nhìn từ trên) của một cây nhị phân cho trước.
Đối với một cây nhị phân cụ thể, một nút xuất hiện trong top view của nó nếu đó là nút đầu tiên ở khoảng cách ngang (horizontal distance) của nó. Khoảng cách ngang cho nút con trái của nút x là x-1 và cho nút con phải của nút x là x+1.
Để giải quyết bài toán này, chúng ta sẽ thực hiện duyệt theo cấp độ (level order traversal) để lấy được nút trên cùng cho một cấp độ cụ thể trước các nút khác ở cùng cấp độ đó. Ngoài ra, chúng ta sẽ sử dụng kỹ thuật hashing (bảng băm) để kiểm tra xem nút được chọn có hiển thị trong top view hay không.
Ví dụ
#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; }
Kết quả
Top View for the given tree: 23 11 35 68