[C++] SWEA 1231 - 중위순회

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV140YnqAIECFAYD&categoryId=AV140YnqAIECFAYD&categoryType=CODE&problemTitle=1231&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

<풀이>

1. 트리 정보를 입력받는다.

2. 트리를 중위순회해서 얻은 문자열을 출력한다.

 

<해법>

1. 트리 정보 저장 방법

=> 문제에서 트리는 완전 이진탐색으로 주어집니다. 따라서, 배열로 구현할 수 있고 각 노드의 자식들은 (본인 index * 2), (본인 index * 2 + 1)로 나타낼 수 있습니다.(루트노드를 index 0이라고 할 때)

 

#include <iostream>
#include <string.h>
 
using namespace std;
 
int N;
char tree[101];
string answer;
 
string inOrderSearch(int idx) {
    if (idx > N) return "";
 
    string ret = "";
    ret = inOrderSearch(idx * 2) + tree[idx] + inOrderSearch((idx * 2) + 1);
    return ret;
}
 
void solution() {
    answer = inOrderSearch(1);
}
 
int main() {
    int test_case;
    int T;
    T = 10;
    for (test_case = 1; test_case <= T; test_case++) {
        //초기화
        N = 0;
        memset(tree, NULL, sizeof(tree));
        answer = "";
 
        //입력
        cin >> N;
        for (int i = 0; i < N; i++) {
            int idx;
            char c;
            cin >> idx >> c;
            tree[idx] = c;
 
            int trash;
            while (getc(stdin) == ' ') {
                cin >> trash;
            }
        }
 
        //해법
        solution();
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
    //종료
    return 0;
}

 

중위순회에 대해 알아볼 수 있는 문제였습니다.