[1991] 트리순회

// 1991 트리순회
// 이진트리 -> map, pair 이용
#include <bits/stdc++.h>

using namespace std;

int n;
map<char, pair<char, char>> tree;

char a, b, c;

void preorder(char node){ // 전위순회
    cout << node;
    if(tree[node].first != '.'){
        preorder(tree[node].first);
    }
    if(tree[node].second != '.'){
        preorder(tree[node].second);
    }
}

void inorder(char node){ // 중위순회
    if(tree[node].first != '.'){
        inorder(tree[node].first);
    }
    cout << node;
    if(tree[node].second != '.'){
        inorder(tree[node].second);
    }
}

void postorder(char node){ // 후위순회
    if(tree[node].first != '.'){
        postorder(tree[node].first);
    }
    if(tree[node].second != '.'){
        postorder(tree[node].second);
    }
    cout << node;
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n; // 노드의 수: 1 ~ 26
    
    for(int i=0; i<n; i++){
        // 노드의 수만큼 map에 저장
        // 노드의 이름은 A부터 차례대로 알파벳 대문자
        cin >> a >> b >> c;
        tree[a] = make_pair(b, c);
    }
    
    // 항상 A가 루트노드
    preorder('A');
    cout << "\n";
    inorder('A');
    cout << "\n";
    postorder('A');
    
    return 0;
}