백준 1991 트리 순회 Kotlin

: ) YOUNG·2023년 6월 17일
1

알고리즘

목록 보기
210/417
post-thumbnail

백준 1991번
https://www.acmicpc.net/problem/1991

문제




생각하기


  • 트리 문제이다.

  • 트리 구조를 만드는게 처음이라서 조금 어려웠다.

  • 트리 순회를 그대로 출력하기만 하면된다.


동작


    repeat(N) {
        val st = StringTokenizer(br.readLine())

        val node: Char = st.nextToken()[0]
        val left: Char = st.nextToken()[0]
        val right: Char = st.nextToken()[0]
        insertNode(head, node, left, right)
    }

노드가 하나씩 들어오면서 insertNode()함수를 통해서 계속 삽입하게 된다.



private fun insertNode(temp: Node?, root: Char, left: Char, right: Char) {
    if (temp?.node == root) {
        if (left == '.') {
            temp.leftNode = null
        } else {
            temp.leftNode = Node(left, null, null)
        }

        if (right == '.') {
            temp.rightNode = null
        } else {
            temp.rightNode = Node(right, null, null)
        }
    } else {
        if (temp?.leftNode != null) {
            insertNode(temp.leftNode!!, root, left, right)
        }
        if (temp?.rightNode != null) {
            insertNode(temp.rightNode, root, left, right)
        }
    }
} // End of insertNode

insertNode()에서는 마치 LinkedList 구조 처럼 Nodeclass를 하나씩 연결해가면서 좌우를 타고 타고 가도록 연결시켜놓았다.



코드


Kotlin


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

// input
private lateinit var br: BufferedReader
private lateinit var sb: StringBuilder

// variables
private var N = 0
private var head = Node('A', null, null)

private data class Node(var node: Char, var leftNode: Node?, var rightNode: Node?) // End of Node

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.`out`))
    sb = StringBuilder()

    input()

    preOrder(head)
    sb.append('\n')

    inOrder(head)
    sb.append('\n')

    postOrder(head)

    bw.write(sb.toString())
    bw.close()
} // End of main

private fun input() {
    N = br.readLine().toInt()

    repeat(N) {
        val st = StringTokenizer(br.readLine())

        val node: Char = st.nextToken()[0]
        val left: Char = st.nextToken()[0]
        val right: Char = st.nextToken()[0]
        insertNode(head, node, left, right)
    }
}// End of input

private fun insertNode(temp: Node?, root: Char, left: Char, right: Char) {
    if (temp?.node == root) {
        if (left == '.') {
            temp.leftNode = null
        } else {
            temp.leftNode = Node(left, null, null)
        }

        if (right == '.') {
            temp.rightNode = null
        } else {
            temp.rightNode = Node(right, null, null)
        }
    } else {
        if (temp?.leftNode != null) {
            insertNode(temp.leftNode!!, root, left, right)
        }
        if (temp?.rightNode != null) {
            insertNode(temp.rightNode, root, left, right)
        }
    }
} // End of insertNode

private fun preOrder(node: Node?) {
    if(node == null) return
    sb.append(node.node)
    preOrder(node.leftNode)
    preOrder(node.rightNode)
} // End of preOrder

private fun inOrder(node : Node?) {
    if(node == null) return
    inOrder(node.leftNode)
    sb.append(node.node)
    inOrder(node.rightNode)
} // End of inOrder

private fun postOrder(node : Node?) {
    if(node == null) return
    postOrder(node.leftNode)
    postOrder(node.rightNode)
    sb.append(node.node)
} // End of postOrder

0개의 댓글