[PS] BOJ5639 이진 검색 트리 ( treeTraveral ) with JAVA

5639번: 이진 검색 트리

 

 

◎ 문제풀이

 

전위순회 결과를 가지고 이진트리를 만든 후 후위순회를 하는 문제이다. 

 

전위순회는 ROOT -> LEFT -> RIGHT 순으로 탐색한다. 그러므로 가장 위에 있는 값이 ROOT이고 다음 값은 LEFT이다. 그리고 그 다음 값은 LEFT의 LEFT이다. LEFT의 LEFT가 없다면 ROOT의 RIGHT이다. 이 구조는 객체참조구조를 이용하면 쉽게 구할 수 있다. 

 

 

◎ 코드

package org.example.tree;


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

//BOJ5639 이진 검색 트리
public class Tree2 {

    public static class Node{
        int num;
        Node left, right;

        public Node(int num){
            this.num = num;
        }

        //객체 참조 구조를 이용
        public void insert(int value){
            if( value < this.num ){  // ROOT 보다 작으면 LEFT
                if( left == null) {
                    left = new Node(value);
                }else{
                    this.left.insert(value);
                }
            }

            else{ // ROOT 보다 크면 RIGHT
                if( right == null ){
                    right = new Node(value);
                }
                else {
                    this.right.insert(value);
                }
            }
        }
    }

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

        int num = Integer.parseInt(br.readLine());
        Node root = new Node(num);

        while(true){
            String input = br.readLine();
            if(input == null || input.equals("")) break;

            root.insert(Integer.parseInt(input));
        }

        postOrder(root);

    }
    
    // 후의 순회
    public static void postOrder(Node root){
        if(root == null) return;

        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root.num); 
    }
}