[C++] 백준 알고리즘 1991 트리 순회
[C] 트리 : 이진트리의 전위, 중위, 후위, 레벨 순회 (tistory.com)
[C] 트리 : 이진트리의 전위, 중위, 후위, 레벨 순회
아까 이진트리를 구현할 때 10 / \ 20 30 위와 같은 트리를 어떻게 순회해야 잘 순회했다고 소문이 날까? 여기엔 크게 3가지 순회가 있다. 전위 순회란 루트를 방문하고 왼쪽 서브트리, 오른쪽 서
sxyzn.tistory.com
위 게시글에서 트리의 순회에 대해 알아보았다.
C로 풀었던 트리의 순회를 C++에서는 map을 이용하여 풀 수 있다.
map은 파이썬에서의 딕셔너리와 비슷한 자료구조이다. key - value 쌍으로 저장이 되며, key 값을 정렬된 상태로 저장한다.
pair라는 것도 있는데, 이것은 두 값을 저장할 수 있다. 이 때에는 pair의 왼쪽 값을 first, 오른쪽 값을 second라고 접근한다.
map에 pair를 사용해보자.
map<int, pair<int,int>> tree;
를 쓰면, tree의 key에 특정 값이 들어올 수 있고,
tree[key값].first 를 이용하면 트리의 왼쪽 값을 접근할 수 있다.
first를 이진 트리의 left, second를 이진 트리의 right라고 생각하고 문제를 풀어보자.
1991번: 트리 순회
첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파
www.acmicpc.net
위 문제는 전위, 중위, 후위 순회를 구하는 문제이다.
풀이는 아래와 같다.
#include <iostream>
#include <map>
using namespace std;
map<char,pair<int, int>> tree;
//전위 순회
void preorder(char c){
if(c=='.')
return;
cout<<c;
preorder(tree[c].first);
preorder(tree[c].second);
}
//중위 순회
void inorder(char c){
if(c=='.')
return;
inorder(tree[c].first);
cout<<c;
inorder(tree[c].second);
}
//후위 순회
void postorder(char c){
if(c=='.')
return;
postorder(tree[c].first);
postorder(tree[c].second);
cout<<c;
}
int main(){
int n;
char root, left, right;
cin>>n;
while(n--){
cin>>root>>left>>right;
tree[root].first=left;
tree[root].second=right;
}
//전위 순회
preorder('A');
cout<<'\n';
//중중위 순회
inorder('A');
cout<<'\n';
//후위 순회
postorder('A');
cout<<'\n';
}