유년

유년

개발자

[SWEA] 1231. 중위순회 (C++, 라이브러리 X)

Tree 기본문제

풀이

자식 유무에 따라서 input 개수가 달라짐.

cin.get() 함수로 줄바꿈 문자인지 체크.

(cin.get()은 한문자씩 입력받고, 공백 문자나 개행 문자를 생략하지 않음.)

Inorder 함수를 이용하여 in-order 형식으로 Tree 순회.

(왼쪽 자식 트리 순회 후, 자기 자신 출력, 마지막으로 오른쪽 자식 트리 순회)

코드 GitHub

#include <iostream>
using namespace std;

#define MAXN 100

int N;

struct Node {
    char alpha;
    int children[2];
} nodes[MAXN];

char text[MAXN];
int textCnt;

void Inorder(int idx) {
    if(nodes[idx].children[0] != -1) Inorder(nodes[idx].children[0]);
    text[textCnt++] = nodes[idx].alpha;
    if(nodes[idx].children[1] != -1) Inorder(nodes[idx].children[1]);
    return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("input.txt", "r", stdin);
    for(int tc = 1; tc <= 10; tc++) {
        cin >> N;
        for(int n = 0; n < N; n++) {
            int idx;
            cin >> idx;
            idx--;
            char alpha;
            cin >> alpha;
            int children[2] = {0, };
            if(cin.get() != '\n') {
                cin >> children[0];
                if(cin.get() != '\n') cin >> children[1];
            }
            children[0]--;
            children[1]--;
            nodes[idx].alpha = alpha;
            nodes[idx].children[0] = children[0];
            nodes[idx].children[1] = children[1];
        }
        textCnt = 0;
        Inorder(0);
        cout << '#' << tc << ' ';
        for(int i = 0; i < textCnt; i++) cout << text[i];
        cout << '\n';
    }
    return 0;
}

댓글남기기