5639번

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

5639번: 이진 검색 트리

오늘 풀은 문제는 이진 트리 검색이다.

저번에 풀은 트리 순회 문제와 순회 방식은 같지만 입력 받는 값들이 전위 순회로 출련된 값들이 주어진다.

그래서 트리를 클래스형으로 구성할 때 조건문을 신경써야 한다.

또한 이 문제는 입력받는 노드의 수가 정해져있지 않아서

입력값이 null인지를 확인하여 반복을 멈추어야한다.

그래서 이 문제는 입력에 주의하여 이진 트리를 생성하는 것이 관건이다.

 

이진트리는 왼쪽 자식에는 부모보다 작은 값, 오른쪽 쪽 자식에는 부모보다 큰 값을 저장하는 트리이기 때문에 이 조건을 이용하여 조건문을 작성해 주었다.

추가로 재귀를 사용하면 가능하다.

 

동작 방식은

1. 부모 노드보다 작은 값인가 확인한다.

2. 작다면 왼쪽 자식이 비어있는지 확인한다.

3. 비어있으면 넣고, 비어있지 않으면 왼쪽 자식을 탐색한다.

1. 부모 노드보다 큰 값인가 확인한다.

2. 크다면 오른쪽 자식이 비어있는지 확인한다.

3. 비어있으면 넣고, 비어있지 않으면 오른쪽 자식을 탐색한다.

 

후위 순회는 알고있을 거라 생각하여 설명은 생략한다.

(왼쪽 자식 노드, 오른쪽 자식 노드, 부모 노드 순)

 

정답코드는 아래와 같다.

package backjoon.b5639;

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

public class b5639 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Node root = new Node(Integer.parseInt(br.readLine()));
        Graph g = new Graph(root);

        while (true){
            String sData = br.readLine();

            if(sData==null) {
                break;
            }
            if(sData.length()==0){
                break;
            }
            g.create(Integer.parseInt(sData));
        }
        g.postOrder(root);
        System.out.println(g.sb);
    }
}
class Graph{
    Node root;
    StringBuilder sb;

    public Graph(Node root) {
        this.root = root;
        sb = new StringBuilder();
    }
    public void create(int data){
        search(root,data);
    }
    public void search(Node node, int data){
        if(node==null){
            return;
        }
        if(node.data>data){
            if(node.left==null){
                node.left = new Node(data);
            }
            else{
                search(node.left,data);
            }
        }
        else if(node.data<data){
            if(node.right==null){
                node.right = new Node(data);
            }
            else {
                search(node.right,data);
            }
        }
    }
    public void postOrder(Node node){
        if(node!=null){
            if(node.left!=null)postOrder(node.left);
            if(node.right!=null)postOrder(node.right);
            sb.append(node.data).append("\n");
        }
    }
}
class Node{
    Node right;
    Node left;
    int data;

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