[BOJ][1991] 트리 순회

1. 문제 링크

https://www.acmicpc.net/problem/1991

2. 사용 알고리즘

트리

3. 풀이

왼쪽 자식노드를 arr[parent][0], 오른쪽 자식노드를 arr[parent][1]에 저장 후 재귀를 돌며 순회하여 출력

4. 소스 코드

4-1. C++

https://github.com/dev-aiden/problem-solving/blob/main/boj/1991.cpp

#include <iostream>

using namespace std;

int arr[33][2];

void preOrder(int start) {
    if(start == -1) return;
    cout << (char)(start + 'A');
    preOrder(arr[start][0]);
    preOrder(arr[start][1]);
}

void inOrder(int start) {
    if(start == -1) return;
    inOrder(arr[start][0]);
    cout << (char)(start + 'A');
    inOrder(arr[start][1]);
}

void postOrder(int start) {
    if(start == -1) return;
    postOrder(arr[start][0]);
    postOrder(arr[start][1]);
    cout << (char)(start + 'A');
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n; for(cin >> n; n--;) {
        char c1, c2, c3; cin >> c1 >> c2 >> c3;
        if(c2 == '.') arr[c1 - 'A'][0] = -1;
        else arr[c1 - 'A'][0] = c2 - 'A';
        if(c3 == '.') arr[c1 - 'A'][1] = -1;
        else arr[c1 - 'A'][1] = c3 - 'A';
    }
    preOrder(0);
    cout << "\n";
    inOrder(0);
    cout << "\n";
    postOrder(0);
    cout << "\n";
    return 0;
}

4-2. JAVA

https://github.com/dev-aiden/problem-solving/blob/main/boj/1991.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int[][] arr = new int[33][2];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        for(int n = Integer.parseInt(br.readLine()); n-- > 0;) {
            st = new StringTokenizer(br.readLine());
            char c1 = st.nextToken().charAt(0);
            char c2 = st.nextToken().charAt(0);
            char c3 = st.nextToken().charAt(0);
            if(c2 == '.') arr[c1 - 'A'][0] = -1;
            else arr[c1 - 'A'][0] = c2 - 'A';
            if(c3 == '.') arr[c1 - 'A'][1] = -1;
            else arr[c1 - 'A'][1] = c3 - 'A';
        }
        StringBuilder sb = new StringBuilder();
        preOrder(0, sb);
        sb.append("\n");
        inOrder(0, sb);
        sb.append("\n");
        postOrder(0, sb);
        sb.append("\n");
        System.out.println(sb);
    }

    static void preOrder(int start, StringBuilder sb) {
        if(start == -1) return;
        sb.append((char)(start + 'A'));
        preOrder(arr[start][0], sb);
        preOrder(arr[start][1], sb);
    }

    static void inOrder(int start, StringBuilder sb) {
        if(start == -1) return;
        inOrder(arr[start][0], sb);
        sb.append((char)(start + 'A'));
        inOrder(arr[start][1], sb);
    }

    static void postOrder(int start, StringBuilder sb) {
        if(start == -1) return;
        postOrder(arr[start][0], sb);
        postOrder(arr[start][1], sb);
        sb.append((char)(start + 'A'));
    }
}