728x90
1. 문제
이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.
예를 들어 위와 같은 이진 트리가 입력되면,
- 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
- 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
- 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)
2. 풀이
1. tree는 [N][2]칸 배열을 사용해서 각 노드마다 자식 둘을 저장할 수 있도록 했다.
2. 무조건 자식 노드에서 'A'를 뺐다. 자식이 없으면 '.'-'A'=-19가 된다.
3. 전위는 부모 먼저, 중위는 부모를 중간으로, 후위는 부모를 나중에 탐색한다.
4. 자식이 있을때만 재귀호출하는데, 자식이 있는지는 그 칸이 0이상인것으로 판단한다.
- 코드에서의 조건은 tree[i][자식] > 0이다. A(값이 0)는 언제나 루트노드이기 때문에 오류없이 동작한다.
import java.io.*;
import java.util.*;
public class BOJ_1991_트리순회 {
static StringBuilder sb = new StringBuilder();
static int[][] tree;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(in.readLine());
StringTokenizer st;
tree = new int[N][2];
for(int i=0;i<N;i++){
//.에서 A빼면 -19
st = new StringTokenizer(in.readLine());
int node = st.nextToken().charAt(0)-'A';
tree[node][0] = st.nextToken().charAt(0)-'A';
tree[node][1] = st.nextToken().charAt(0)-'A';
}
preorder(0);
sb.append('\n');
inorder(0);
sb.append('\n');
postorder(0);
System.out.println(sb);
}
private static void preorder(int i) {
sb.append((char)(i+'A'));
if(tree[i][0]>0) preorder(tree[i][0]);
if(tree[i][1]>0) preorder(tree[i][1]);
}
private static void inorder(int i) {
if(tree[i][0]>0) inorder(tree[i][0]);
sb.append((char)(i+'A'));
if(tree[i][1]>0) inorder(tree[i][1]);
}
private static void postorder(int i) {
if(tree[i][0]>0) postorder(tree[i][0]);
if(tree[i][1]>0) postorder(tree[i][1]);
sb.append((char)(i+'A'));
}
}
3. 결과
트리탐색의 베이직 같은 문제였다.
'코딩테스트 > BOJ' 카테고리의 다른 글
[BOJ] 14499 주사위 굴리기 - JAVA (0) | 2022.04.11 |
---|---|
[BOJ] 5639 이진검색트리 - JAVA (0) | 2022.04.10 |
[BOJ] 14502 연구소 - JAVA (0) | 2022.04.08 |
[BOJ] 3190 뱀 - JAVA (0) | 2022.04.07 |
[BOJ] 17471 게리맨더링 - JAVA (0) | 2022.04.07 |
댓글