Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình in tất cả các nút xuất hiện trong chế độ xem trên cùng của một cây nhị phân nhất định.
Đối với một cây nhị phân cụ thể, một nút xuất hiện trong chế độ xem trên cùng của nó nếu nó là nút đầu tiên ở khoảng cách ngang của nó. Khoảng cách ngang đối với nút bên trái của nút x là x-1 và đối với nút bên phải của nút x là x + 1.
Để giải quyết vấn đề này, chúng ta sẽ thực hiện duyệt thứ tự cấp để chúng ta có được nút trên cùng cho một cấp cụ thể trước khi các nút khác có mặt ở cấp đó. Hơn nữa, chúng tôi sẽ sử dụng hàm băm để kiểm tra xem nút đã chọn có hiển thị ở chế độ xem trên cùng 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;
} Đầu ra
Top View for the given tree: 23 11 35 68