[BOJ][Java] 1991번 트리 순회

문제 설명

문제 링크 : https://www.acmicpc.net/problem/1991

 

이 문제는 이진트리를 활용해서 푸는 문제이다.

문제에 들어가기 전 이진 트리에 대해 알아보자

 

이진 트리에는 편향 이진 트리, 포화 이진 트리, 완전 이진 트리가 있다.

편향 이진 트리는 노드들이 한쪽으로 편향돼 생성된 이진 트리이고,

포화 이진 트리는 트리의 높이가 모두 일정하며 리프 노드가 꽉 찬 이진 트리,

완전 이진 트리는 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은

왼쪽부터 채워진 트리이다.

 

보통 이렇게 트리를 배열로 표현하는 것이 일반적인데 이렇게 했을 때

편리한 점은 아래 정리한 표와 같이 부모 노드, 자식 노드들의 인덱스값을 편하게 계산할 수 있다.

이동 목표 노드	인덱스 연산	제약 조건(N = 노드 개수)
루트 노드	index = 1
부모 노드	index = index / 2	루트 노드가 아닐 때
왼쪽 자식 노드	index = index * 2	index * 2 <= N
오른쪽 자식 노드	index = index * 2 + 1	index * 2 + 1 <= N

 

 

해당 문제를 풀기 위해 우선 배열을 초기화 해준다.

이때 각 문자(char) 타입을 정수형 (int)으로 변환하여 저장한다.

 

전위 순회를 예로 살펴보면 위와 같이 노드의 흐름이 나온다. 우선 루트 노드를 찍고

이후 왼쪽 자식노드가 존재하면 해당 노드로 갔다가 존재하지 않는다면 오른쪽 자식노드로 가는 방식이다.

재귀함수를 활용해 전위, 중위, 후위 순회 모두 구현할 수 있다.

 

package boj;

import java.io.*;

public class BOJ1991 {
    static int[][] arr;
    static StringBuilder sb;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        arr = new int[27][2];
        for(int i = 0; i < N; i++){
            char[] temp = br.readLine().toCharArray();

            int node = temp[0] - 'A';
            char left = temp[2];
            char right = temp[4];

            if(left == '.') arr[node][0] = -1;
            else arr[node][0] = left - 'A';

            if(right == '.') arr[node][1] = -1;
            else arr[node][1] = right - 'A';
        }

        sb = new StringBuilder();
        preOrder(0);
        System.out.println(sb);

        sb = new StringBuilder();
        inOrder(0);
        System.out.println(sb);

        sb = new StringBuilder();
        postOrder(0);
        System.out.println(sb);


    }
    static void preOrder(int node){
        if(node == -1) return;

        sb.append((char)(node + 'A'));
        preOrder(arr[node][0]);
        preOrder(arr[node][1]);
    }

    static void inOrder(int node){
        if(node == -1) return;

        inOrder(arr[node][0]);
        sb.append((char)(node + 'A'));
        inOrder(arr[node][1]);

    }

    static void postOrder(int node){
        if(node == -1) return;

        postOrder(arr[node][0]);
        postOrder(arr[node][1]);
        sb.append((char)(node + 'A'));
    }
}