Today I Learned

오늘도 코틀린 코테 공부!!

트리 순회

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

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.
첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

• 입력
  7
  A B C
  B D .
  C E F
  E . .
  F . G
  D . .
  G . .
• 출력
  ABDCEFG
  DBAECFG
  DBEGFCA

문제 풀이

• 코테 문제라기보단 트리 순회를 구현하는 문제에 가깝다. 자바로는 예전에 했던 기억이 어렴풋이 있는데 코틀린으로 시도해보았다.

1. Node 클래스를 만들어 data, left, right 값을 가지게 한다. left와 right는 null이 가능하게 ?로 처리한다.

2. 전위, 중위, 후위 순회는 재귀로 구현한다. 전위순회는 값을 먼저 출력한 뒤에 좌,우를 탐색한다. 중위순회는 좌측을 먼저 탐색하고 값을 출력한 뒤 우측 탐색을 한다. 후위순회는 좌,우 탐색을 먼저 하고 값을 출력한다.

3. main 함수에서 값을 입력받아 mutableMap을 이용해 트리를 받아준다. 입력에 관한 사항들을 처리해주어 진행한다. root는 항상 A로 시작한다.

4. 전위,중위,후위를 각각의 함수를 이용해 출력하면 완료!

Kotlin 코드

class Node(var data: Char, var left: Node? = null, var right: Node? = null)

fun preorder(node: Node?) {
    if (node != null) {
        print(node.data)
        preorder(node.left)
        preorder(node.right)
    }
}

fun inorder(node: Node?) {
    if (node != null) {
        inorder(node.left)
        print(node.data)
        inorder(node.right)
    }
}

fun postorder(node: Node?) {
    if (node != null) {
        postorder(node.left)
        postorder(node.right)
        print(node.data)
    }
}

fun main() {
    val n = readln().toInt()
    val tree = mutableMapOf<Char, Node>()

    repeat(n) {
        val (parent, left, right) = readln().split(" ")
        if (!tree.containsKey(parent[0])) {
            tree[parent[0]] = Node(parent[0])
        }
        if (left != ".") {
            if (!tree.containsKey(left[0])) {
                tree[left[0]] = Node(left[0])
            }
            tree[parent[0]]!!.left = tree[left[0]]
        }
        if (right != ".") {
            if (!tree.containsKey(right[0])) {
                tree[right[0]] = Node(right[0])
            }
            tree[parent[0]]!!.right = tree[right[0]]
        }
    }

    val root = tree.values.first()
    preorder(root)
    println()
    inorder(root)
    println()
    postorder(root)
}