트리 순회 연습

Main.kt

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

/**
 *         1
 *        /\
 *       2 3
 *      /\  \
 *     4 5   6
 */
fun main() {
    val root = Node(1, Node(2, Node(4, null, null), Node(5)), Node(3, null, Node(6)))

    print("전위순회: ") // 1 2 4 5 3 6
    printPreorder(root)
    println()

    print("중위순회: ") // 4 2 5 1 3 6
    printInorder(root)
    println()

    print("후위순회: ") // 4 5 2 6 3 1
    printPostorder(root)
}

/**
 * 전위순회(Preorder Traversal) | 깊이 우선 순회(DFT, Depth-First Traversal)
 * 왼쪽 -> 오른쪽 순으로 노드를 방문
 * 주로 트리를 복사하거나 트리의 높이를 구하는 등의 연산에 사용
 */
fun printPreorder(node: Node?) {
    if (node == null) {
        return
    }
    print("${node.data} ")

    printPreorder(node.left)
    printPreorder(node.right)
}

/**
 * 중위순회(Inorder Traversal) | 대칭 순회(symmetric traversal)
 * 왼쪽 -> 루트 -> 오른쪽 순으로 노드를 방문
 * 주로 트리의 노드를 오름차순으로 정렬된 순서로 방문할 때 사용(특히 이진탐색트리, BST)
 */
fun printInorder(node: Node?) {
    if (node == null) {
        return
    }

    printInorder(node.left)

    print("${node.data} ")

    printInorder(node.right)
}

/**
 * 후위순회(Postorder Traversal)
 * 왼쪽 -> 오른쪽 -> 루트 순으로 노드를 방문
 * 주로 트리의 노드를 삭제할 때 사용
 */
fun printPostorder(node: Node?) {
    if (node == null) {
        return
    }

    printPostorder(node.left)
    printPostorder(node.right)

    print("${node.data} ")
}