[JAVA] 백준 5639 트리 순회

 

 

 

5639번: 이진 검색 트리

문제

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

풀이

이진 탐색 트리의 전위 순회한 결과가 주어졌을 때, 트리를 후위 순회해야 하기 때문에 먼저 전위순회한 결과를 이진 탐색트리로 바꿔주었고 바꾼 트리를 다시 후위 순회하여 결과를 출력하였습니다.

📌 값 입력받기

        String value = "";
        while (true){
            value = br.readLine();
            if(value == null || value.equals("")) break;
            A.add(Integer.parseInt(value));
        }

트리의 요소가 몇개인지 알 수 없었기 때문에 ArrayList에 값을 추가해주었고 종료 지점도 만들어주었습니다.

📌 트리 구현

    static class Node{
        int value;
        Node left;
        Node right;

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

        }
    }

트리를 구현하기 위해 왼쪽, 오른쪽이 있는 노드를 하나 만들었습니다.

📌 전위 순회 결과를 이진 탐색 트리로 바꾸기

        Node root = new Node(A.get(0));
        for(int i=1; i<A.size(); i++){
            Node now = root;
            int target = A.get(i);
            while (true){
                if(now.value > target){
                    if(now.left == null){
                        now.left = new Node(target);
                        break;
                    }else{
                        now = now.left;
                    }
                }else if(now.value < target){
                    if(now.right == null){
                        now.right = new Node(target);
                        break;
                    }else{
                        now = now.right;
                    }
                }
            }
        }

루트 노드를 먼저 정의해주고 루트 노드를 기준으로 내려가면서 값의 위치를 찾아주었습니다.

1. 만약 현재 노드의 값보다 입력된 값이 작다면
   1. 위의 가정이 맞고 만약 현재 노드의 왼쪽이 비어있다면, 값을 추가해주고 break로 반복을 종료한다.
   2. 위의 가정이 맞고 만약 현재 노드의 왼쪽에 값이 있다면, 현재 위치를 왼쪽으로 변경한다.
2. 만약 현재 노드의 값보다 입력된 값이 크다면
   1. 위의 가정이 맞고 만약 현재 노드의 오른쪽이 비어있다면, 값을 추가해주고 break로 반복을 종료한다.
   2. 위의 가정이 맞고 만약 현재 노드의 오른쪽에 값이 있다면, 현재 위치를 오른쪽으로 변경한다.

📌 후위 순회

     public static void postOrder(Node now){
        if(now == null) return;

        postOrder(now.left);
        postOrder(now.right);

        System.out.println(now.value);

    }

루트를 기준으로 왼쪽 노드, 오른쪽 노드, 현재 노드 순서대로 값을 출력해주었습니다.

📌 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static ArrayList<Integer> A = new ArrayList<>();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String value = "";
        while (true){
            value = br.readLine();
            if(value == null || value.equals("")) break;
            A.add(Integer.parseInt(value));
        }

        Node root = new Node(A.get(0));
        for(int i=1; i<A.size(); i++){
            Node now = root;
            int target = A.get(i);
            while (true){
                if(now.value > target){
                    if(now.left == null){
                        now.left = new Node(target);
                        break;
                    }else{
                        now = now.left;
                    }
                }else if(now.value < target){
                    if(now.right == null){
                        now.right = new Node(target);
                        break;
                    }else{
                        now = now.right;
                    }
                }
            }
        }
        postOrder(root);

    }

    public static void postOrder(Node now){
        if(now == null) return;

        postOrder(now.left);
        postOrder(now.right);

        System.out.println(now.value);

    }

    static class Node{
        int value;
        Node left;
        Node right;

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

        }
    }

}

결과