백준 5639 이진 검색 트리

·2022년 3월 8일
0

문제

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

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

  • 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
  • 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.
이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

코드

import java.io.*;

class Main {
    static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

    public static class Tree{
        int value;
        Tree left;
        Tree right;

        public Tree(int value){
            this.value=value;
            left=null;
            right=null;
        }

        public static void insert(Tree head, int value) {
            Tree temp = new Tree(value);
            Tree ptr = head;

            while(true){
                if(value>ptr.value) {
                    if (ptr.right == null) {
                        ptr.right = temp;
                        return;
                    } else
                        ptr = ptr.right;
                }
                else {
                    if (ptr.left == null) {
                        ptr.left = temp;
                        return;
                    } else
                        ptr = ptr.left;
                }
            }
        }

        public static void postorder(Tree ptr) throws IOException {
            if(ptr==null)
                return;

            postorder(ptr.left);
            postorder(ptr.right);
            bw.write(ptr.value+"\n");
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        String s=br.readLine();
        Tree head=new Tree(Integer.parseInt(s));
        while(true){
            s=br.readLine();
            if(s==null)
                break;
            if(s.equals(""))
                break;

            Tree.insert(head, Integer.parseInt(s));
        }

        Tree.postorder(head);
        bw.flush();
    }
}

해결 과정

  1. Binary Search Tree를 만들어서 입력 받는 값을 넣은 뒤 Postorder Traversal 해서 출력했다. 입력의 끝을 알 수가 없어서 BufferedReaderreadline 메소드를 사용한 뒤 s의 값을 null과 비교해줘서 탈출 시켰다.

  2. 런타임 에러(탈출 했을 때 마지막 문자열은 ""인 상태이므로 parseInt("")에서 런타임 에러가 발생한다. 따라서 조건을 추가해줬다.)

  3. 😁

profile
渽晛

0개의 댓글