[백준] 1991 트리 순회

www.acmicpc.net/problem/1991

1991번: 트리 순회

2020-11-15

---

import java.util.Scanner;

public class Main1991 {
	public static int N;
	public static char arr[][];

	public static void preorder(char ch) {
		System.out.print(ch);
		if(arr[ch-'A'][0] != '.') preorder(arr[ch-'A'][0]);
		if(arr[ch-'A'][1] != '.') preorder(arr[ch-'A'][1]);
	}

	public static void inorder(char ch) {
		if(arr[ch-'A'][0] != '.') inorder(arr[ch-'A'][0]);
		System.out.print(ch);
		if(arr[ch-'A'][1] != '.') inorder(arr[ch-'A'][1]);
	}

	public static void postorder(char ch) {
		if(arr[ch-'A'][0] != '.') postorder(arr[ch-'A'][0]);
		if(arr[ch-'A'][1] != '.') postorder(arr[ch-'A'][1]);
		System.out.print(ch);
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		arr = new char[27][2];

		for (int i = 0; i < N; i++) {
			char a = sc.next().charAt(0);
			char b = sc.next().charAt(0);
			char c = sc.next().charAt(0);
			arr[a - 'A'][0] = b; // left
			arr[a - 'A'][1] = c; // right
		}
		
		preorder('A');
		System.out.println();
		inorder('A');
		System.out.println();
		postorder('A');
	}
}

 

1. 2차원 배열을 정의하고 arr[node][0]에는 노드의 왼쪽 자식 노드 값, arr[node][1]에는 오른쪽 자식 노드 값을 저장한다.

 

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

 

2. preorder는 루트->왼쪽자식->오른쪽자식 순으로 순회한다.

루트 : A

왼쪽자식 : B -> D

오른쪽자식 : C -> E -> F -> G

 

3. inorder는 왼쪽자식->루트->오른쪽자식 순으로 순회한다.

왼쪽자식 : D -> B

루트 : A

오른쪽자식 : E -> C -> F -> G

 

4. postorer는 왼쪽자식->오른쪽자식->루트 순으로 순회한다.

왼쪽자식 : D -> B

오른쪽자식 : E -> G -> F -> C

루트 : A