[JAVA] 이진 트리 백준 BOJ 1991 전위 순회, 중위 순회, 후위 순회

 

이진 트리(binary tree) 는 각 노드의 자식 노드(차수)의 개수가 2 이하로 구성되어 있는 트리입니다. 트리 영역에서 가장 많이 사용됩니다.

 

이진 트리 핵심

이진 트리 종류

이진 트리는 크게 아래 세 개로 나뉩니다.

그림만으로도 각각의 특징을 대충 느낌을 잡을 수 있을 텐데요.

 

편향 이진 트리(Skewed Binary Tree)

 

• 같은 높이의 이진 트리 중에서 최소 개수의 노드 개수를 가짐.
• 왼쪽 혹은 오른쪽 서브트리만을 가지는 이진트리.

 

포화 이진 트리(Full Binary Tree)

 

• 모든 레벨의 노드가 꽉 차있는 이진 트리.
• N = 2ᴴ  - 1 을 만족한다. (N: 노드의 개수, H: 트리의 높이)

 

완전 이진 트리(Complete Binary Tree)

 

• 트리의 높이가 H 일 때 레벨 1 부터 레빌 (H-1) 까지는 노드가 포화 이진 트리처럼 꽉 채워져 있고 마지막 레벨 H 에서는 중간에 빈 노드 없이 노드가 왼쪽부터 차례대로 채워져 있는 이진 트리
• N < 2ᴴ - 1 을 만족한다. (N: 노드의 개수, H: 트리의 높이)

 

데이터를 트리 자료 구조에 저장할 때 편향 이진 트리의 형태로 저장하면 속도도 느리고 공간도 낭비됩니다. 일반적으로 데이터를 트리에 담는다고 하면 완전 이진 트리에 담는다는 것을 의미합니다.

 

트리 자료 구조

가장 직관적이면서 편리한 트리 자료 구조 형태는 '배열' 입니다.

 

 

 

이진 트리는 위처럼 1차원 배열의 형태로 표현할 수 있습니다. 

 

1차원 배열에서 트리의 노드와 배열의 인덱스 관계

노드	인덱스 연산	제약 조건(N = 노드 개수)
루트 노드	index = 1
부모 노드	index = index / 2	현재 노드가 루트 노드가 아닐 때.
왼쪽 자식 노드	index = index * 2	index * 2 ≦ N. (자식 노드를 가질 수 있는 조건)
오른쪽 자식 노드	index = index * 2 + 1	index * 2 + 1 ≦ N. (자식 노드를 가질 수 있는 조건)

 

보통 코딩 테스트에서 트리 문제가 나오면 그래프의 표현 방식(인접 리스트, 에지 리스트, 등) 보다 위처럼 데이터를 담는 것이 일반적이기 때문에 꼭 이해해야 합니다.

위 인덱스 연산 방식은 세그먼트 트리(Segment Tree) , LCA(Lowest Common Ancestor) 알고리즘에서 기본이 되는 연산입니다.

 

백준 1991 트리 순회

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

1991번: 트리 순회



1. 문제 분석

문제가 요구하는 자료구조 형태만 충실하게 구현하면 됩니다.

문제에서 주어진 입력값을 트리 형태의 자료 구조에 적절하게 저장하고, 그 안에서 탐색을 수행하는 로직을 구현합니다.

 

클래스로 노드를 구현할 수도 있고 2차원 배열로 구현할 수도 있을 것 같네요. 2차원 배열로 해봅시다.

2. 손으로 풀기

a. 2차원 배열에 트리 데이터를 저장합니다.

b. 각각 전위 순회, 중위 순회, 후위 순회 함수를 구현합니다.

세 함수 모두 재귀 함수 형태로 구현하면 될 것 같네요.

 

 

 

3. 슈도코드

N: 노드 개수
H: 트리의 높이: 2³ = 8 < 7 일 때 H == 3
bw: BufferedWriter
tree: 2차원 배열. 왼쪽 자식과 오른쪽 자식을 가지도록.
tree[N][0] -> 왼쪽 자식
tree[N][1] -> 오른쪽 자식 

트리 데이터 입력받기

전위 순회
bw.write('\n')
중위 순회
bw.write('\n')
후위 순회

bw.flush
bw.close

// 전위 순회
preorderTrav(int node){
    현재 노드를 bw 에 쓰기
    만약 node 가 왼쪽 자식이 있다면
        preorderTrav(왼쪽 자식)
    만약 node 가 오른쪽 자식이 있다면
        preorderTrav(오른쪽 자식)
}

// 중위 순회
inorderTrav(int node){
    만약 node 가 왼쪽 자식이 있다면
        inorderTrav(왼쪽 자식)
    현재 노드를 bw 에 쓰기
    만약 node 가 오른쪽 자식이 있다면
        inorderTrav(오른쪽 자식)
}

// 후위 순회
postorderTrav(int node){
    만약 node 가 왼쪽 자식이 있다면
        postorderTrav(왼쪽 자식)
    만약 node 가 오른쪽 자식이 있다면
        postorderTrav(오른쪽 자식)
    현재 노드를 bw 에 쓰기
}

4. 코드

public class BeakJun1991 {
    static BufferedWriter bw;
    static int[][] tree;

    public static void main(String[] args) throws IOException {
        input();

        preorder(1);
        bw.write('\n');
        inorder(1);
        bw.write('\n');
        postorder(1);

        bw.flush();
        bw.close();
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        tree = new int[N + 1][2];

        for (int i = 0; i < N; i++) {
            char[] line = br.readLine().toCharArray();
            int parent = line[0] - 'A' + 1;
            int lChildStr = line[2];
            int rChildStr = line[4];
            if (lChildStr != 46) {
                tree[parent][0] = lChildStr - 'A' + 1;
            }
            if (rChildStr != 46) {
                tree[parent][1] = rChildStr - 'A' + 1;
            }
        }
        br.close();
    }

    static void preorder(int node) throws IOException {
        bw.write((char) node + 'A' - 1);
        if (tree[node][0] != 0)
            preorder(tree[node][0]);
        if (tree[node][1] != 0)
            preorder(tree[node][1]);

    }

    static void inorder(int node) throws IOException {
        if (tree[node][0] != 0)
            inorder(tree[node][0]);
        bw.write((char) node + 'A' - 1);
        if (tree[node][1] != 0)
            inorder(tree[node][1]);
    }

    static void postorder(int node) throws IOException {
        if (tree[node][0] != 0)
            postorder(tree[node][0]);
        if (tree[node][1] != 0)
            postorder(tree[node][1]);
        bw.write((char) node + 'A' - 1);
    }
}