[Java] 백준 이진 검색 트리

1. 문제분석

전위 순회한 결과값으로 후위 순회를 한 값을 출력하는 문제다.

전위 순회는 (왼쪽 -> 루트 -> 오른쪽), 후위 순회는(왼쪽 -> 오른쪽 -> 루트)로 순회한다.

하지만 데이터를 넣을 때도 순회한 순서대로 넣어줘야할까?

 

위의 세가지 조건을 보자.

1. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.

2. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.

3. 왼쪽, 오른쪽 서브트리도 이진 검색 트리다.

 

어찌 됐던 데이터가 들어갈 때, 위의 조건대로 만들어진다.

결과적으로 전위 순회한 값 순서대로 넣어주면 우리가 원하는 트리 모습이 나오고 그 트리로 후위 순회를 한다.

2. 구현

import java.io.*;

class Node {
    int value;
    Node left, right;

    Node(int value) {
        this.value = value;
    }

    //트리 조건
    void insert(int value) {
        //루트보다 작다면?
        if (value < this.value) {
            //왼쪽에 넣을 준비
            if (this.left == null) {
                this.left = new Node(value);
            }
            //그 값보다 작다면?
            else {
                //왼쪽에 넣어줌
                this.left.insert(value);
            }
        } else {
            if (this.right == null) {
                this.right = new Node(value);
            } else {
                this.right.insert(value);
            }
        }
    }
}

public class Main {

    static StringBuilder sb = new StringBuilder();

    static void postOrder(Node node) {
        //후위 순회는 왼쪽 -> 오른쪽 -> 루트 (루트가 나올 때 출력)
        if (node == null) return;
        if (node.left != null) postOrder(node.left);
        if (node.right != null) postOrder(node.right);
        sb.append(node.value).append("\n");
    }

    public static void main(String[] args) throws IOException {
        //BufferedReader 로 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Node root = new Node(Integer.parseInt(br.readLine()));
        while (true) {
            String inputValue = br.readLine();
            if (inputValue == null) {
                break;
            }
            root.insert(Integer.parseInt(inputValue));
        }
        postOrder(root);
        System.out.println(sb);
    }
}

트리 클래스를 만들어서 구현했다.

insert의 조건은 아까 위에서 본 3가지 조건으로 구현을 했다.

그리고 inputValue가 ""이면 될 줄 알았는데 null로 처리해야 오류가 나지 않는다.

 

후위 순회는 앞서 말한 것 처럼 왼쪽 -> 오른쪽 -> 루트다.

후위 순회를 재귀로 구현하는 것은 간단하다. 다른 순회 방법도 루트일 때 출력을 해주면 된다.

3. 마무리

알고리즘 공부를 할 때, 항상 트리를 무서워했다. 정말 이해가 가지 않는다..

이번 기회로 트리를 좀 더 알아갔으면 좋겠다.