BST 구현

백준 1991번을 Java를 이용하여 풀어보았다. 트리를 다뤄보는 건 학교 자료구조 수업 시간에 대충 성적 받기용으로만 어설프게 한 후로 처음이었다. 뭐 아예 몰랐다고 해도 되겠다. 프로그래머스 카카오 블라인드 문제를 풀다가 트리 문제가 나왔는데 트리에 대한 지식이 전무해서 백준 트리 문제부터 풀어봐야겠다 싶어서 풀었다.

문제 링크 첨부한다.
https://www.acmicpc.net/problem/1991

---

이진 탐색 트리 구현

크게 새로운 노드를 추가해주는 add()와 search()를 구현하고 문제 조건대로 전위순회, 중위순회 그리고 후위순회로 출력하는 메소드를 구현했다.

먼저 add()와 search()를 아래 코드로 함께 살펴보자.

class Tree {
        Node root; // 모든 트리에는 root 노드가 있다. 클래스 변수로 선언하자

        void add(char data, char leftData, char rightData) {
            if (root == null) { // 루트가 아직 비어있으면
                root = new Node(data);
                if (leftData != '.') root.left = new Node(leftData);
                if (rightData != '.') root.right = new Node(rightData);
            } else search(root, data, leftData, rightData); // 들어갈 자리를 찾아주자
        }

        void search(Node curNode, char data, char leftData, char rightData) {
            if (curNode == null) return; // 끝까지 왔는데 자리 없으면 종료
            else if(curNode.data == data){ // 자리 찾음!!
                if (leftData != '.') curNode.left = new Node(leftData);
                if (rightData != '.') curNode.right = new Node(rightData);
            }
            else{
                search(curNode.left, data, leftData, rightData);
                search(curNode.right, data, leftData, rightData);
            }
        }

        ...
    }

add()

root 노드가 비어있을 때와 이미 있을 때를 구분해서 수행하자. 비어있으면 root 노드를 채워주고, 차 있으면 들어갈 자리를 찾아줄 search()를 수행하자.

search()

왼쪽 재귀 검색과 오른쪽 재귀 검색을 통해서 새롭게 추가해주는 노드가 어디 위치해야 할지를 찾아주자.

위의 두 재귀를 수행해서 마지막 curNode.left 또는 curNode.right까지 찾아갔는데 만약 더이상 갈 곳이 없어 비어있는 ==null이라면 자리가 없는 놈이기 때문에 종료를 해주면 된다.

자리를 찾았으면 왼쪽과 오른쪽 노드를 연결해주면 된다.

---

순회 방식에 따른 출력 메소드

문제에서 요구한 것은 preorder, inorder 그리고 postorder 순서로 출력하는 것이었다.
아래 코드를 통해 살펴보자.

class Tree {
        Node root;

        ...

        void preorder(Node curNode) throws IOException { // root -> left -> right
            bfw.write(curNode.data+"");
            if(curNode.left!=null)  preorder(curNode.left);
            if(curNode.right!=null) preorder(curNode.right);
        }

        void inorder(Node curNode) throws IOException { // left -> root -> right
            if(curNode.left!=null)  inorder(curNode.left);
            bfw.write(curNode.data+"");
            if(curNode.right!=null) inorder(curNode.right);
        }

        void postorder(Node curNode) throws IOException { // left -> right -> root
            if(curNode.left!=null)  postorder(curNode.left);
            if(curNode.right!=null) postorder(curNode.right);
            bfw.write(curNode.data+"");
        }
    }

root 노드를 어느 타이밍에 출력해줄지만 한 칸씩 옮기면 되는 것이다.

---

BST를 처음 구현해보고 순회 방식에 따라 출력 메소드도 만들어 보았다. 또다른 트리 문제를 만나면 그때는 혼자의 힘으로 해결해보자. 아래는 내가 제출한 코드다.

import java.util.*;
import java.io.*;

public class boj1991 {
    static BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String args[]) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(bfr.readLine());
        Tree tree = new Tree();

        int n = Integer.parseInt(stk.nextToken());
        for (int i = 0; i < n; i++) {
            stk = new StringTokenizer(bfr.readLine());
            tree.add(stk.nextToken().charAt(0), stk.nextToken().charAt(0), stk.nextToken().charAt(0));
        }
        tree.preorder(tree.root);   bfw.newLine();
        tree.inorder(tree.root);    bfw.newLine();
        tree.postorder(tree.root);
        bfw.close();
    }

    static class Node {
        char data;
        Node left;
        Node right;

        Node(char data) {
            this.data = data;
        }
    }

    static class Tree {
        Node root;

        void add(char data, char leftData, char rightData) {
            if (root == null) { // 루트가 아직 비어있으면
                root = new Node(data);
                if (leftData != '.') root.left = new Node(leftData);
                if (rightData != '.') root.right = new Node(rightData);
            } else search(root, data, leftData, rightData); // 들어갈 자리를 찾아주자
        }

        void search(Node curNode, char data, char leftData, char rightData) {
            if (curNode == null) return; // 끝까지 왔는데 자리 없으면 종료
            else if(curNode.data == data){
                if (leftData != '.') curNode.left = new Node(leftData);
                if (rightData != '.') curNode.right = new Node(rightData);
            }
            else{
                search(curNode.left, data, leftData, rightData);
                search(curNode.right, data, leftData, rightData);
            }
        }

        void preorder(Node curNode) throws IOException {
            bfw.write(curNode.data+"");
            if(curNode.left!=null)  preorder(curNode.left);
            if(curNode.right!=null) preorder(curNode.right);
        }

        void inorder(Node curNode) throws IOException {
            if(curNode.left!=null)  inorder(curNode.left);
            bfw.write(curNode.data+"");
            if(curNode.right!=null) inorder(curNode.right);
        }

        void postorder(Node curNode) throws IOException {
            if(curNode.left!=null)  postorder(curNode.left);
            if(curNode.right!=null) postorder(curNode.right);
            bfw.write(curNode.data+"");
        }
    }
}