[G5] 이진 검색 트리 : Java : 5639 - Tree

---

시도 방법

방법 1 : 위로 올라가면서 비교 (실패)

1. 전위 탐색으로 노드 값이 주어진다
2. 마지막 삽입 노드를 기준으로 추가 해야지
3. 마지막으로 삽입된 노드를 기준으로 점점 올라가면서 비교를 하자
4. "틀렸습니다"

방법 2 : 루트를 기준으로 아래로 내려가면서 적절한 위치에 삽입 (성공)

1. 모든 트리의 왼쪽은 무조건 자기보다 작아야 하고 오른쪽은 무조건 커야하는 규칙이 존재
2. 루트를 기준으로 내려가면서 적절한 위치에 노드를 추가하면 되지 않을까
3. "맞았습니다"

 

의문점

왜 하나씩 추가해도 문제가 되지 않는지 이해가 안되어서 찾아봄

의문점 1 : 이진 탐색트리는 값에 따라 위치가 무조건 같나? 삽입 순서에 따라 달라지는 건가?
답 : 삽입 순서에 따라 위치는 물론 트리 모양도 달라짐

의문점 2: 하나씩 추가해도 되는 방법이라면 값에 따라 트리의 모양이 같아야 하는데? 전위 탐색과는 무슨 연관이지?
답 : 전위 탐색으로 노드가 주어지기 때문에 순서는 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순으로 만 주어짐.
하지만 입력 데이터는 일렬로 주어지기 때문에 어떤 노드의 왼쪽이고 오른쪽이고 알 수 없음. 하지만 왼쪽은 작고, 오른쪽은 크다는 규칙을 통해 왼쪽, 오른쪽을 구분 할 수 있음.

 

결론

루트를 기준으로 아래로 비교하면서 하나씩 추가 하는 것이 가능한 이유는 전위 탐색 결과(무조건 루트, 왼쪽, 오른쪽 순)가 주어지고, 왼쪽과 오른쪽을 구분할 수 있는 이진 검색 트리의 특징 이 있기 떄문.

 

 

문제 풀이

1. 전위 순회이므로 처음 나온 것이 root

2. root를 기준으로 재귀적으로 내려가면서 작으면 left, 크면 right에 삽입

3. 완성된 tree를 후위 순회로 출력

 

코드

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



public class Main {
    static Node root;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String strN;

        // 입력 데이터가 없을 때까지 입력 받음
        while((strN = br.readLine()) != null && !strN.isEmpty()){
            if(root == null){
                // root 생성
                root = new Node(Integer.parseInt(strN));
                continue;
            }

            Node curNode = new Node(Integer.parseInt(strN));
            insertNode(root, curNode);
        }

        // 후위 순회
        postOrder(root);

        br.close();
    }

    static void insertNode(Node root, Node insertedNode){
        // 왼쪽으로
        if(root.value > insertedNode.value){
            if(root.left == null){
                root.left = insertedNode;
                return;
            }
            insertNode(root.left, insertedNode);
        }

        // 오른쪽으로
        else if(root.value < insertedNode.value){
            if(root.right == null){
                root.right = insertedNode;
                return;
            }
            insertNode(root.right, insertedNode);
        }
    }

    static void postOrder(Node node){
        if(node.left != null){
            postOrder(node.left);
        }
        if(node.right != null){
            postOrder(node.right);
        }
        System.out.println(node.value);
    }

}

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

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


}