[백준] 1992 - 트리순회

1. 구조체 배열로 입력을 받아서 부모노드를 기준으로 오름차순 정렬

2. 왼쪽, 오른쪽으로 구분하여 재귀호출로 트리 생성

3. pre, in, pos 순으로 순회하며 출력

#include <iostream>
#include <algorithm>
using namespace std;
 
typedef struct NODE {
    char c;
    int end;
    NODE *L;
    NODE *R;
}node;
 
struct MAP {
    char c1, l, r;
}map[30];
 
int N;
 
bool com(const MAP i, const MAP j)
{
    return i.c1 < j.c1;
}
 
node *makenewnode() {
    node *tmp = (node*)malloc(sizeof(node));
    tmp->c = 0;
    tmp->end = 0;
    tmp->L = 0;
    tmp->R = 0;
    return tmp;
}
 
void insert(node *root, char buf)
{
    node*tmp = root;
    if (buf == '.') { tmp->end = 1; return; }
    tmp->c = buf;
    tmp->L = makenewnode();
    tmp->R = makenewnode();
    insert(tmp->L, map[buf-'A'].l);
    insert(tmp->R, map[buf-'A'].r);
}
 
void pre(node*root)
{
    if (root->end) return;
    cout << root->c;
    pre(root->L);
    pre(root->R);
}
 
void ino(node *root)
{
    if (root->end) return;
    ino(root->L);
    cout << root->c;
    ino(root->R);
}
 
void pos(node*root)
{
    if (root->end) return;
    pos(root->L);
    pos(root->R);
    cout << root->c;
}
 
int main(void)
{
    cin >> N;
    node*root = makenewnode();
    for (int i = 0; i < N; i++)
        cin >> map[i].c1 >> map[i].l >> map[i].r;
    sort(map, map + N, com);
    insert(root, map[0].c1);
    pre(root);    cout << endl;
    ino(root);    cout << endl;
    pos(root);    cout << endl;
    return 0;
}