백준 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 구조 처럼 Node
class를 하나씩 연결해가면서 좌우를 타고 타고 가도록 연결시켜놓았다.
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