이 튜토리얼에서는 주어진 이진 트리의 상위 뷰에 나타나는 모든 노드를 인쇄하는 프로그램에 대해 논의할 것입니다.
특정 이진 트리의 경우 노드가 수평 거리에서 맨 처음 노드인 경우 상위 뷰에 노드가 나타납니다. 노드 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