[백준] 1991번: 트리순회 C++ 풀이

접근:

트리를 이용해서 푸는 문제

트리를 순회하는 순서만 생각하면 된다.

 

전략:

우선 트리 저장을 배열 형태로 저장하는데, 저장 방식은 다양하나

나는 각 알파벳을 숫자로 치환해서 저장하도록 하겠다.

(공간을 많이 잡아먹지 않는 문제이기 때문에, 편한 대로 쓰도록 하겠다. 즉, 최적화된 건 아님)

순회할 때 필요한 정보는 현재 위치와 자식 노드의 유무이다.

 

구현:

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

struct Node{
    int left;
    int right;
};

vector<Node*> nod;

int n;
int c2n(char a){
    return (a != '.') ? static_cast<int>(a - 'A') : -1;
}
char n2c(int a){
    return (a + 'A');
}

void preorder(int cur){
    cout << n2c(cur);
    if(nod[cur]->left != -1) preorder(nod[cur]->left);
    if(nod[cur]->right != -1) preorder(nod[cur]->right);
}
void postorder(int cur){
    if(nod[cur]->left != -1) postorder(nod[cur]->left);
    if(nod[cur]->right != -1) postorder(nod[cur]->right);
    cout << n2c(cur);
}
void inorder(int cur){

    if(nod[cur]->left != -1) inorder(nod[cur]->left);
    cout << n2c(cur);
    if(nod[cur]->right != -1) inorder(nod[cur]->right);
}

int main(){
    cin >> n;
    nod.resize(n+1);
    for(int i=0;i<n;i++){
        char cur, l,r;
        cin >> cur >> l >> r;
        nod[c2n(cur)] = new Node{c2n(l), c2n(r)};
    }
    preorder(0);cout <<'\n';
    inorder(0);cout <<'\n';
    postorder(0);cout <<'\n';
    return 0;
}