문제

---

이진 트리를 입력받아 전위,중위,후위 순회한 결과를 출력하는 프로그램을 만드시오

• 전위순회한 결과 : ABDCEFG
• 중위순회한 결과 : DBAECFG
• 후위순회한 결과 : DBEGFCA

입력

---

첫째 줄에는 트리의 노드의 개수 N(1이상 26이하)
둘째 줄부터 N개의 줄에 걸쳐 각 노드와 해당 노드의 왼쪽 자식, 오른쪽 자식이 주어진다.
노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다.
자식 노드가 없는 경우 .으로 표시한다.

출력

---

전위,중위,후위 순회한 결과를 차례대로 출력한다.

제한

---

• 시간 제한 : 2초
• 메모리 제한 : 128MB
  
  
  
  

풀이

---

1. 노드의 값과 자식 노드를 저장할 이차원 배열을 생성하고 입력값을 저장한다.
   1.1 int[][] arr = new int[27][2];
   배열의 길이 = [알파벳의 수+1][자식 노드 2개]로 정한다.
   예를 들어, 입력값이 B E G 인 경우 해당 노드의 값은 B, 자식노드들의 값은 E,G이다.
   이때, 배열에 입력되는 값은 arr['B'-'A'+1][0] = 'E'-'A'+1, arr['B'-'A'][1] = 'G'-'A'+1이다. 만약, 자식 노드가 없어 .이 입력된다면 값을 0으로 저장한다.

2. 전위순회 메서드를 실행한다.
   2.2 전위순회는 루트 - 왼쪽자식 - 오른쪽자식 순으로 출력되므로 재귀호출을
   현재노드 출력 - 왼쪽 자식 재귀호출 - 오른쪽 자식 재귀호출 순서로 진행된다.

private static void preOrder(int node) {
	if(node == 0) {
    	return;
    }
    
    System.out.print((char)(node+'A'-1));
    preOrder(arr[node][0]);
    preOrder(arr[node][1]);
}

3. 중위순회 메서드를 실행한다.
   2.2 중위순회는 왼쪽자식 - 루트 - 오른쪽자식 순으로 출력되므로 재귀호출을
   왼쪽 자식 재귀호출 - 현재노드 출력 - 오른쪽 자식 재귀호출 순서로 진행된다.

private static void inOrder(int node) {
	if(node == 0) {
    	return;
    }
    
    inOrder(arr[node][0]);
    System.out.print((char)(node+'A'-1));
    inOrder(arr[node][1]);
}

4. 후위순회 메서드를 실행한다.
   2.2 후위순회는 왼쪽자식 - 오른쪽자식 - 루트 순으로 출력되므로 재귀호출을
   왼쪽 자식 재귀호출 - 오른쪽 자식 재귀호출 - 현재노드 출력 순서로 진행된다.

private static void postOrder(int node) {
	if(node == 0) {
    	return;
    }
    
    postOrder(arr[node][0]);
    postOrder(arr[node][1]);
    System.out.print((char)(node+'A'-1));
}

최종 코드

---

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

public class Main {

    private static int[][] arr;
    private static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        arr = new int[27][2];
        char value;
        char leftNode;
        char rightNode;

        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            value = st.nextToken().charAt(0);
            leftNode = st.nextToken().charAt(0);
            rightNode = st.nextToken().charAt(0);

            if (leftNode != '.') {
                arr[value - 'A'+1][0] = leftNode - 'A'+1;

            }
            if (rightNode != '.') {
                arr[value - 'A'+1][1] = rightNode - 'A'+1;
            }
        }

        preOrder(1);
        sb.append("\n");
        inOrder(1);
        sb.append("\n");
        postOrder(1);

        System.out.println(sb);
    }

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

    }

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

    }

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

결과

---