이 튜토리얼에서는 주어진 이진 트리의 상위 뷰(Top View)에 나타나는 모든 노드를 출력하는 프로그램을 다룹니다.
상위 뷰란 무엇인가?
이진 트리에서 어떤 노드가 상위 뷰에 나타난다는 것은, 트리를 위에서 내려다볼 때 해당 노드가 자신의 수평 거리(horizontal distance) 위치에서 가장 먼저 보이는 노드, 즉 그 위치에서 가장 위쪽에 있는 노드라는 의미입니다.
수평 거리는 다음과 같이 정의됩니다.
- 노드 x의 왼쪽 자식 노드의 수평 거리 = x - 1
- 노드 x의 오른쪽 자식 노드의 수평 거리 = x + 1
접근 방법
이 문제는 레벨 순서 순회(level order traversal)와 해싱(hash map)을 조합하여 효율적으로 해결할 수 있습니다.
- 레벨 순서 순회(BFS): 큐(queue)를 사용해 트리를 위에서부터 한 레벨씩 순회합니다. 이렇게 하면 같은 수평 거리에 여러 노드가 존재하더라도 항상 더 위쪽에 있는 노드를 먼저 처리하게 됩니다.
- 해시 맵으로 중복 확인: 각 노드의 수평 거리를 키(key)로 사용하여, 해당 거리가 아직 맵에 기록되어 있지 않을 때만 현재 노드의 값을 저장합니다. 이미 값이 있다면 그 노드는 더 위쪽 노드에 가려져 상위 뷰에 보이지 않습니다.
- 결과 출력: 순회가 끝나면 맵은 키(수평 거리)를 기준으로 자동 정렬되므로, 왼쪽에서 오른쪽 순서로 상위 뷰 노드들을 출력할 수 있습니다.
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
동작 원리 살펴보기
예제 트리에서 루트 노드 11의 수평 거리는 0입니다. 왼쪽 자식 23은 -1, 오른쪽 자식 35는 +1의 수평 거리를 가집니다. 노드 47, 59, 68은 오른쪽으로 계속 이어지며 수평 거리 0, +1, +2에 위치하지만, 레벨 순서 순회의 특성상 이미 더 위쪽에 있는 노드(11, 35)가 먼저 맵에 기록되었기 때문에 상위 뷰에서 제외됩니다. 마지막으로 수평 거리 +2에 처음 등장하는 68만 추가됩니다.
따라서 최종 출력은 왼쪽부터 오른쪽 순서로 23 11 35 68이 됩니다.