BOJ S1 1881 트리순회 JAVA

1991번: 트리 순회

---

문제 읽기

해당 문제는 트리의 아주 기초적인 문제이다. 최근 트리 문제를 많이 풀지 못해서 어제 코테를 쳤는데 기초적인 트리 문제를 제출하지 못했다! 이게 너무 아쉬워서 오늘부터는 트리 문제를 중점적으로 풀어보려 한다.

---

문제 풀기

해당 문제에서 주어지는 트리는 이진 트리이다. 처음에 트리를 어떻게 저장할 지 고민하다가, 이전에 많이 사용했던 class 방식을 사용하기로 했다.

문제 풀이 과정은 크게 다음과 같다.

1. 트리를 저장할 자료구조를 정의한다.
2. 트리 정보를 입력받으며 트리에 데이터를 삽입한다.
3. preOrder, inOrder, postOrder로 트리를 순회하는 코드를 재귀로 작성한다.

 

트리를 저장할 자료구조

 

나는 class와 포인터 같은 객체를 사용했다. 사실 학부 시절 알고리즘 수업을 들을 때는 C++을 주로 썼기 때문에 포인터 느낌이 왔다. 어쨌든 아래와 같은 class를 만들고 루트 노드를 저장할 객체 하나를 만들었다.

    static class Node{
        char data;
        Node left, right;
        public Node(char data){
            this.data = data;
        }
        public Node(char data, Node left, Node right){
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }
    static Node root = null;

 

데이터를 입력 받아 트리 구조에 삽입하기

 

그 다음은 데이터를 입력 받아 저장할 차례이다. 입력 형태는 다음과 같다.

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

 

(부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드) 형태로 들어오기 때문에, root 노드로부터 부모 노드를 찾아서 왼쪽과 오른쪽 자식 노드를 입력해주는 방식으로 코드를 작성할 수 있다. 즉, 재귀 형태인 것이다.

    private static void insertNode(Node root, char parent, char left, char right) {
        if (root.data == parent){
            //찾았으면 넣어줌
            if (left != '.') root.left = new Node(left);
            if (right != '.') root.right = new Node(right);
            return;
        }

        //아니라면 내려감
        if (root.left != null) insertNode(root.left, parent, left, right);
        if (root.right != null) insertNode(root.right, parent, left, right);
    }

 

트리 순회하기

 

이 다음에는 preOrder, inOrder, postOrder 코드를 작성해야 한다. 사실 세 개는 모두 유사한 ‘재귀’ 과정을 통해 이루어지지만, 출력하는 위치만 다르다고 볼 수 있다.

preOrder

root → left → right 순으로 탐색이 이루어진다.

    private static void preOrder(Node root) {
        System.out.print(root.data);
        if (root.left != null) preOrder(root.left);
        if (root.right != null) preOrder(root.right);
    }

inOrder

left → root → right 순으로 탐색이 이루어진다.

    private static void inOrder(Node root) {
        if (root.left != null) inOrder(root.left);
        System.out.print(root.data);
        if (root.right != null) inOrder(root.right);
    }

postOrder

left → right → root 순으로 탐색이 이루어진다.

    private static void postOrder(Node root) {
        if (root.left != null) postOrder(root.left);
        if (root.right != null) postOrder(root.right);
        System.out.print(root.data);
    }

 

위 과정에 대해 헷갈려 하는 사람이 많은데, root를 기준으로 맨 앞인지, 중간인지, 마지막인지 보면 외우기 쉽다.

이렇게 tree의 기본적인 구조 구성하기, 삽입하기, 순회하기 까지 알아보았다. 내일은 좀 더 어려운 문제를 공부해보자.