백준 - 트리 순회(Kotlin) : 트리를 구현해보는 개념 문제

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/1991

 

[문제 설명]

트리를 순회하라.

 

[접근 방법]

트리를 구현하고, 전위순회, 중위순회, 후위순회를 구현해야 한다.

말이 전위순회, 중위순회, 후위순회지 코드는 엄청 단순하게 나온다.

자료구조 시간에도 많이 나오는 탐색법이므로 구현해서 복습을 해보자.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.StringTokenizer

val bw = BufferedWriter(OutputStreamWriter(System.out))
class Tree(var rootNode: Node?) {
    fun createTree(rootData: Char, lData: Char, rData: Char) {
        if (rootNode != null) {
            return
        }
        rootNode = Node(rootData, null, null)
        if (lData != '.') {
            rootNode!!.left = Node(lData, null, null)
        }
        if (rData != '.') {
            rootNode!!.right = Node(rData, null, null)
        }
    }

    fun addNode(rootData: Char, lData: Char, rData: Char) {
        // rootData를 찾음
        val node = rootNode?.let { searchNode(it, rootData) }
        node?.let {
            if (lData != '.') {
                node.left = Node(lData, null, null)
            }
            if (rData != '.') {
                node.right = Node(rData, null, null)
            }
        }
    }

    // startNode부터 재귀 탐색을 통해 data와 일치하는 node를 리턴한다
    private fun searchNode(startNode: Node, data: Char): Node? {
        var result: Node? = null
        if (startNode == null) {
            return null
        } else if (startNode.data == data) {
            return startNode
        }

        startNode.left?.let {
            result =  searchNode(it, data)
        }
        result?.let { return result }

        startNode.right?.let {
            result = searchNode(it, data)
        }

        return result
    }

    fun preOrder(node: Node) {
        bw.write(node.data.toString())
        if (node.left != null) {
            preOrder(node.left!!)
        }
        if (node.right != null) {
            preOrder(node.right!!)
        }
    }

    // 중위 순회
    fun inOrder(node: Node) {
        node.left?.let {
            inOrder(it)
        }
        bw.write(node.data.toString())
        node.right?.let {
            inOrder(it)
        }
    }

    // 후위 순회
    fun postOrder(node: Node) {
        node.left?.let {
            postOrder(it)
        }
        node.right?.let {
            postOrder(it)
        }
        bw.write(node.data.toString())
    }
}

class Node(val data: Char, var left: Node?, var right: Node?)
fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val cntOfNode = br.readLine().toInt()
    var st = StringTokenizer(br.readLine())
    // 루트 노드 만들기
    val tree = Tree(null)
    tree.createTree(st.nextToken()[0], st.nextToken()[0], st.nextToken()[0])

    // 트리 만들기
    repeat(cntOfNode - 1) {
        st = StringTokenizer(br.readLine())
        tree.addNode(st.nextToken()[0], st.nextToken()[0], st.nextToken()[0])
    }

    tree.rootNode?.let { rootNode ->
        tree.preOrder(rootNode)
        bw.write("\n")
        bw.flush()
        tree.inOrder(rootNode)
        bw.write("\n")
        bw.flush()
        tree.postOrder(rootNode)
        bw.write("\n")
        bw.flush()
    }
}