코딩테스트/BOJ

[BOJ] 1991 트리순회 - JAVA

5월._. 2022. 4. 9.
728x90

1. 문제

 

1991번: 트리 순회

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파

www.acmicpc.net

이진 트리를 입력받아 전위 순회(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

댓글