[백준 5639번][Kotlin] 이진 검색 트리

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

5639번: 이진 검색 트리

 

난이도 : 골드 4
태그 : 그래프 이론, 그래프 탐색, 트리, 재귀

 

 

설명

입력으로 pre order(전위 순회)가 주어지고, 이를 트리 형태로 변환하여

post order(후위 순회)하여 방문한 노드 순서대로 출력하는 문제입니다.

 

 

소스코드

전체 소스코드

import java.io.BufferedReader
import java.io.InputStreamReader

val sb = StringBuilder()

data class Node(val value: Int, var left: Node?, var right: Node?) {
    fun addChildNode(n: Int) {
        if (n > value) {
            // right가 비어있을 때 새 노드 삽입
            if (right == null) right = Node(n, null, null)
            // right가 있을 때 오른쪽 자식 노드로 가서 addChildNode 수행
            else right!!.addChildNode(n)
        } else {
            // left가 비어있을 때 새 노드 삽입
            if (left == null) left = Node(n, null, null)
            // left가 있을 때 왼쪽 자식 노드로 가서 addChildNode 수행
            else left!!.addChildNode(n)
        }
    }
}

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))

    val root = Node(br.readLine().toInt(), null, null)

    while (true) {
        val input = br.readLine() ?: break // 입력값이 없을 때 break
        val n = input.toInt()
        root.addChildNode(n)
    }

    postOrder(root)
    println(sb)
}

fun postOrder(node: Node?) {
    if (node != null) {
        // post order (후위 순회) 시 왼쪽 -> 오른쪽 -> 루트
        postOrder(node.left)
        postOrder(node.right)
        sb.append(node.value).append("\n")
    }
}

 

전체 소스코드입니다. 하나씩 살펴보겠습니다.

 

 

노드 클래스

data class Node(val value: Int, var left: Node?, var right: Node?) {
    fun addChildNode(n: Int) {
        if (n > value) {
            // right가 비어있을 때 새 노드 삽입
            if (right == null) right = Node(n, null, null)
            // right가 있을 때 오른쪽 자식 노드로 가서 addChildNode 수행
            else right!!.addChildNode(n)
        } else {
            // left가 비어있을 때 새 노드 삽입
            if (left == null) left = Node(n, null, null)
            // left가 있을 때 왼쪽 자식 노드로 가서 addChildNode 수행
            else left!!.addChildNode(n)
        }
    }
}

Node 데이터 클래스입니다.

값을 담는 value와, 왼쪽, 오른쪽 자식 노드가 있고,

노드에 자식 노드를 추가하는 addChildNode 메소드가 있습니다.

 

addChild 메소드는 입력으로 받은 값(n)이 해당 노드의 값(value)보다 크다면,

오른쪽 자식 노드에, 작다면 왼쪽 자식 노드에 추가합니다.

 

오른쪽 자식 노드가 존재하지 않는다면,

새 자식 노드를 생성합니다.

 

만약 자식 노드가 이미 존재하고 있다면, 해당 자식노드의 addChildNode를 호출하여

재귀적으로 작동합니다.

 

이는 왼쪽 자식노드 역시 마찬가지로 작동됩니다.

 

 

postOrder - 후위 순회

fun postOrder(node: Node?) {
    if (node != null) {
        // post order (후위 순회) 시 왼쪽 -> 오른쪽 -> 루트
        postOrder(node.left)
        postOrder(node.right)
        sb.append(node.value).append("\n")
    }
}

 

후위 순회를 진행하는 부분입니다.

노드가 null이 아닐 경우 진행하며,

왼쪽 노드 - 오른쪽 노드 - 루트 순으로 진행하는 포스트 오더에 맞게

 

postOrder(node.left) -> postOrder(node.right) -> 해당 노드 값 출력 순으로 이루어집니다.

이렇게 한다면 재귀적으로 가장 왼쪽 노드부터 탐색을 하고, 그 다음 오른쪽 노드, 그 다음 부모 노드를 탐색하게 됩니다.

 

 

 

후기

트리의 구조와 탐색 등은 자료구조 수업때 정말 지겹도록 공부했는데,

재귀를 통해 탐색 과정을 코드로 구현하는 건 잘 해보질 않았던 것 같네요.

 

앞으로는 이론만이 아니라 직접 코드로 구현해보는 과정도 같이 해야 할 것 같습니다.