1991번: 트리 순회
첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자
www.acmicpc.net
트리 순회의 간단한 문제입니다.
input으로 주어지는 노드는 A~Z까지 26개이므로 숫자로 변환하여 인덱스화 하였습니다.
list배열에 각 노드의 왼쪽자식을 [0]에, 오른쪽 자식을 [1]에 저장하여 순회하였습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | package BOJ.data_structure; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Boj1991 { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static StringBuffer sb = new StringBuffer(); static int list[][] = new int[27][2]; static int N; static void preorder(int v) { sb.append((char) (v + 'A')); if (list[v][0] != -1) preorder(list[v][0]); if (list[v][1] != -1) preorder(list[v][1]); } static void inorder(int v) { if (list[v][0] != -1) inorder(list[v][0]); sb.append((char) (v + 'A')); if (list[v][1] != -1) inorder(list[v][1]); } static void postorder(int v) { if (list[v][0] != -1) postorder(list[v][0]); if (list[v][1] != -1) postorder(list[v][1]); sb.append((char) (v + 'A')); } static void input() throws Exception { st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); for (int i = 0; i < N; i++) { st = new StringTokenizer(br.readLine()); char x = st.nextToken().charAt(0); char l = st.nextToken().charAt(0); char r = st.nextToken().charAt(0); if (l == '.') list[x - 'A'][0] = -1; else list[x - 'A'][0] = l - 'A'; if (r == '.') list[x - 'A'][1] = -1; else list[x - 'A'][1] = r - 'A'; } } public static void main(String[] args) throws Exception { input(); preorder(0); sb.append("\n"); inorder(0); sb.append("\n"); postorder(0); sb.append("\n"); System.out.println(sb.toString()); } } | cs |
'algorithm > data-structure' 카테고리의 다른 글
| boj 4358 생태학 (0) | 2021.01.25 |
|---|---|
| boj 5639 이진 검색 트리 (0) | 2021.01.24 |
| boj 11003 최솟값 찾기 (0) | 2021.01.22 |
| boj 1517 버블 소트 (0) | 2021.01.22 |
| boj 2517 달리기 (0) | 2021.01.22 |