[TREE] 백준 1991 트리 순회(Tree Order)

BackJoon 

#1991 - 트리순회(Tree Order)

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

이번 시간은 트리 순회에 대해서 알아보겠습니다. 트리 순회는 3가지 방법으로 트리를 순회할 수 있습니다.

각 순회 방법에 따라 루트 탐색 순서가 어떤지 파악하면, 쉽게 암기 할 수 있습니다. 

다음과 같은 트리가 있다고 가정하면, 각 순회 방법에 따라 탐색 순서가 바뀝니다.

1. 전위 순회

 루트 - > Left -> Right  // ABDCEFG

2. 중위 순회

 Left -> 루트 -> Right // DBAECFG

3. 후위 순회

 Left -> Right - > 루트 // DBEGFCA

이제 재귀함수 호출을 통해 전위, 중위, 후위 순회를 구현해보겠습니다. 입력 값이 알파벳이기 때문에 알파벳 ABC ... Z 까지 총 26개를 배열 0~25개에 저장을 어떻게 하는지 유심히 보시면 좋겠습니다. 또한 a[i][0], a[i][1] 은 i번째 알파벳에 해당하는 노드의 왼쪽 자식 노드 값(a[i][0]), 오른쪽 자식 노드 값(a[i][1])을 뜻합니다.

package BackJoon.Tree;

import java.util.Scanner;

public class TreeOrder {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		sc.nextLine();// 엔터 제거
		
		//알파벳 총 26개,자식 노드 2개
		int[][] a = new int[26][2];
		for(int i=0; i<n; i++){
			String line = sc.nextLine();
			//문자형에 문자형을 연산하면 결과가 각 문자형의 int값들의 연산과 같다.
			//'A'를 빼주는 이유 0~25까지 26개의 index로 대문자 알파벳을 강제 매칭 시키려고
			int x = line.charAt(0) - 'A'; //부모 알파벳 index값
			char y = line.charAt(2);
			char z = line.charAt(4);
			// '.'인 경우 자식이 없다는 것임. 
			// 자식이 없는 경우 -1 저장.
			if (y == '.') {
                a[x][0] = -1;
            } else {
                a[x][0] = y-'A';
            }
            if (z == '.') {
                a[x][1] = -1;
            } else {
                a[x][1] = z-'A';
            }
		}
		
		
		preorder(a,0); //2번째 인자는 시작할 루트
		System.out.println();
		inorder(a,0);
		System.out.println();
		postorder(a,0);
		System.out.println();
	}


	private static void preorder(int[][] a, int x) {
		if(x == -1)return;
		System.out.print((char)(x+'A'));
		preorder(a, a[x][0]); // Left
		preorder(a, a[x][1]); // Right
	
	}

	private static void inorder(int[][] a, int x) {
		if(x == -1)return;
		inorder(a, a[x][0]); // Left
		System.out.print((char)(x+'A'));
		inorder(a, a[x][1]); // Right
		
	}
	
	private static void postorder(int[][] a, int x) {
		if(x == -1)return;
		postorder(a, a[x][0]); // Left
		postorder(a, a[x][1]); // Right
		System.out.print((char)(x+'A'));
		
	}


}