(1991) 트리 순회

https://www.acmicpc.net/problem/1991

단계별로 풀어보기

33단계(트리) 4번째

 

 

 

이진 트리처럼 최대 자식 수가 적고 노드 수가 그리 많지 않다면 map을 일종의 트리처럼 이용할 수 있다.

(자식 수가 많아도 value를 벡터 등으로 하면 되는데, 이러면 보통 노드 수도 많아서 이 트릭을 쓰기 어렵다.)

그래프나 노드 구조체에 비해 압도적으로 편한 것이 장점이다.

 

 

 

#include <iostream>
#include <map>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int n;
  
  cin >> n;
  
  map<char, pair<char, char>> tree;
  
  while(n--){
    char p, l, r;
    
    cin >> p >> l >> r;
    
    tree[p]= {l, r};
  }
  
  auto order= [&](auto self, char node, int type) -> void {
    if(type==0)  cout << node;
    
    if(tree[node].first!='.')  self(self, tree[node].first, type);
    
    if(type==1)  cout << node;
    
    if(tree[node].second!='.')  self(self, tree[node].second, type);
    
    if(type==2)  cout << node;
  };
  
  order(order, 'A', 0);
  cout << "\n";
  order(order, 'A', 1);
  cout << "\n";
  order(order, 'A', 2);
  
  return 0;
}