백준 1991 트리 순회 / C++

문제 : 1991

풀이 point

순회 방식은 그리 어렵지 않지만 입력을 어떻게 받는지가 중요하다.
입력을 받을 때 부모, 왼쪽 자식, 오른쪽 자식이 주어지는데 그 인덱스에 맞게 연결해주어야만 제대로 된 연결이 된다.

그외 순회는 재귀로 쉽게 구현 가능하다.

풀이 방법

부모 인덱스를 구한 후 부모 인덱스에 맞게 왼쪽, 오른쪽 자식을 배열에 저장해준다.
그 후 재귀로 순회 방식을 구현하면 된다.

undefined
undefined

코드

//백준 1991, 트리 순회

#include <iostream>

int n;
char tree[100][3];

void preorder(int idx){
    if(tree[idx][0] ==  '.') return;
    std::cout << tree[idx][0];
    if(tree[idx][1] != '.') preorder(tree[idx][1] - 'A');
    if(tree[idx][2] != '.') preorder(tree[idx][2] - 'A');
}

void inorder(int idx){
    if(tree[idx][0] ==  '.') return;
    if(tree[idx][1] != '.') inorder(tree[idx][1] - 'A');
    std::cout << tree[idx][0];
    if(tree[idx][2] != '.') inorder(tree[idx][2] - 'A');
}

void postorder(int idx){
    if(tree[idx][0] ==  '.') return;
    if(tree[idx][1] != '.') postorder(tree[idx][1] - 'A');
    if(tree[idx][2] != '.') postorder(tree[idx][2] - 'A');
    std::cout << tree[idx][0];
}

int main(){
    
    std::cin >> n;
    
    for(int i{0}; i<n; ++i){
        char parent, left, right;
        std::cin >> parent >> left >> right;
        int idx = parent - 'A';
        tree[idx][0] = parent;
        tree[idx][1] = left;
        tree[idx][2] = right;
        
    }
    preorder(0); std::cout << '\n';
    inorder(0); std::cout << '\n';
    postorder(0);
    
    
    return 0;
}