물론입니다. 이것도 앞선 글들과 같은 톤으로 존댓말로 자연스럽게 다듬고, 어색한 표현과 설명 흐름을 정리한 완성본으로 적어드리겠습니다.
이미지는 그대로 유지했습니다.
✍ Kotlin을 사용한 PS 문제 풀이를 위한 알고리즘
소속 중인 A&I 동아리에서 코딩 역량을 강화하고자
코딩캠프를 진행하며 작성한 포스트입니다.
해당 포스트는Kotlin을 기반으로 작성하였습니다.
트리
트리(Tree)는 계층 구조를 가지는 특수한 형태의 그래프입니다.
이번 글에서는 그중에서도 이진 트리의 순회 방법에 대해 알아보겠습니다.
PS 문제를 풀다 보면 트리 구조를 직접 다루거나,
트리를 순회하며 원하는 값을 찾는 문제가 자주 등장합니다.
이때 가장 기본이 되는 개념이 바로 트리 순회입니다.
이진 트리
이진 트리는
루트 노드(Root Node)부터 시작하는 트리 구조입니다.
각 노드는 자식 노드를 가질 수 있는데,
이진 트리에서는 한 노드가 가질 수 있는 자식의 수가 최대 2개로 제한됩니다.
보통 자식 노드는 다음과 같이 나뉩니다.
- 왼쪽 자식 노드
- 오른쪽 자식 노드
또한 자식이 전혀 없는 노드는 리프 노드(Leaf Node) 라고 부릅니다.
즉, 이진 트리는 부모와 자식의 관계가 계층적으로 구성되어 있고,
각 노드가 최대 두 개의 자식을 가진다는 점이 핵심입니다.
트리 순회 방법 3가지
이진 트리의 순회 방법은 대표적으로 다음 3가지가 있습니다.
- 전위 순회(Preorder Traversal)
- 중위 순회(Inorder Traversal)
- 후위 순회(Postorder Traversal)
각 순회는 부모 노드와 자식 노드를 방문하는 순서가 다릅니다.
1. 전위 순회
전위 순회는 부모 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드 순서로 순회합니다.
쉽게 기억하면 [부모 - 왼쪽 - 오른쪽] 입니다.
즉, 현재 노드를 먼저 방문한 뒤
왼쪽 서브트리를 탐색하고,
그다음 오른쪽 서브트리를 탐색하는 방식입니다.
예를 들어보겠습니다
아래와 같은 트리가 있다고 가정해 보겠습니다.
전위 순회에서는 먼저 부모 노드를 방문하고,
그다음 왼쪽 자식을 계속 따라 내려갑니다.
왼쪽 서브트리의 순회를 모두 마쳤다면,
이후 오른쪽 서브트리로 이동하여 같은 방식으로 순회를 이어갑니다.
in Kotlin
전위 순회를 Kotlin으로 구현할 때는
노드 클래스를 만들고, 각 노드가left,right를 가지도록 구성하면 됩니다.
그리고 전위 순회의 핵심은
현재 노드의 값을 먼저 출력한 뒤,
왼쪽과 오른쪽 자식을 재귀적으로 순회하는 것입니다.
class Node(
val data: Char
) {
var left: Node? = null
var right: Node? = null
}
fun preOrderTraversal(node: Node?) {
if (node == null) return
println(node.data)
preOrderTraversal(node.left)
preOrderTraversal(node.right)
}
fun main() {
val a = Node('A')
val b = Node('B')
val c = Node('C')
val d = Node('D')
val e = Node('E')
val f = Node('F')
a.left = b
a.right = c
b.left = d
b.right = e
c.right = f
preOrderTraversal(a)
}실행해 보면 전위 순회의 순서대로 값이 출력되는 것을 확인할 수 있습니다.
2. 중위 순회
중위 순회는 왼쪽 자식 노드 → 부모 노드 → 오른쪽 자식 노드 순서로 순회합니다.
쉽게 기억하면 [왼쪽 - 부모 - 오른쪽] 입니다.
즉, 현재 노드를 바로 방문하지 않고
먼저 왼쪽 서브트리를 모두 순회한 뒤 부모를 방문하고,
마지막으로 오른쪽 서브트리를 순회합니다.
이 방식은 특히 이진 탐색 트리(Binary Search Tree) 에서 자주 등장합니다.
이진 탐색 트리를 중위 순회하면 값이 오름차순으로 출력되기 때문입니다.
예시를 살펴보겠습니다
중위 순회에서는 가장 왼쪽 아래에 있는 리프 노드부터 먼저 방문합니다.
따라서 D가 먼저 나오고,
그다음 부모인 B,
그리고 오른쪽 자식인 E 순서로 방문하게 됩니다.
이후 다시 루트 노드로 올라와 A를 방문하고,
마지막으로 오른쪽 서브트리인 C, F 순서로 순회를 이어갑니다.
in Kotlin
중위 순회는 전위 순회와 구조는 비슷하지만,
출력 위치만 달라집니다.
즉, 왼쪽 자식 → 현재 노드 출력 → 오른쪽 자식 순서로 재귀를 수행하면 됩니다.
class Node(
val data: Char
) {
var left: Node? = null
var right: Node? = null
}
fun inOrderTraversal(node: Node?) {
if (node == null) return
inOrderTraversal(node.left)
println(node.data)
inOrderTraversal(node.right)
}
fun main() {
val a = Node('A')
val b = Node('B')
val c = Node('C')
val d = Node('D')
val e = Node('E')
val f = Node('F')
a.left = b
a.right = c
b.left = d
b.right = e
c.right = f
inOrderTraversal(a)
}
3. 후위 순회
후위 순회는 왼쪽 자식 노드 → 오른쪽 자식 노드 → 부모 노드 순서로 순회합니다.
쉽게 기억하면 [왼쪽 - 오른쪽 - 부모] 입니다.
즉, 부모 노드는 가장 마지막에 방문합니다.
현재 노드보다 먼저 자식 노드들을 모두 처리한 뒤
마지막에 부모 노드를 방문하는 방식입니다.
이 순회 방식은 하위 노드를 먼저 처리해야 하는 상황에서 자주 사용됩니다.
예를 들어 트리를 삭제하거나,
하위 계산 결과를 먼저 구한 뒤 부모에서 활용해야 하는 문제에서 유용합니다.
순회를 살펴보겠습니다
후위 순회는 먼저 왼쪽 자식 노드부터 방문하고,
그다음 오른쪽 자식 노드를 방문한 뒤
마지막으로 부모 노드를 방문합니다.
즉, 루트 노드를 바로 출력하는 것이 아니라
루트의 왼쪽과 오른쪽 서브트리를 모두 순회한 뒤
가장 마지막에 루트 노드를 출력하게 됩니다.
in Kotlin
후위 순회 역시 구조는 동일하지만,
출력 위치를 가장 마지막으로 옮기면 됩니다.
즉, 왼쪽 자식 → 오른쪽 자식 → 현재 노드 출력 순서로 재귀를 수행합니다.
class Node(
val data: Char
) {
var left: Node? = null
var right: Node? = null
}
fun postOrderTraversal(node: Node?) {
if (node == null) return
postOrderTraversal(node.left)
postOrderTraversal(node.right)
println(node.data)
}
fun main() {
val a = Node('A')
val b = Node('B')
val c = Node('C')
val d = Node('D')
val e = Node('E')
val f = Node('F')
a.left = b
a.right = c
b.left = d
b.right = e
c.right = f
postOrderTraversal(a)
}
세 가지 순회 방식 정리
같은 트리라도 순회 방식에 따라 방문 순서는 달라집니다.
- 전위 순회: 부모 → 왼쪽 → 오른쪽
- 중위 순회: 왼쪽 → 부모 → 오른쪽
- 후위 순회: 왼쪽 → 오른쪽 → 부모
즉, 핵심 차이는 부모 노드를 언제 방문하느냐에 있습니다.
- 부모를 먼저 방문하면 전위 순회
- 부모를 중간에 방문하면 중위 순회
- 부모를 마지막에 방문하면 후위 순회
이 차이만 정확히 기억해 두면
트리 순회 문제를 훨씬 쉽게 이해할 수 있습니다.
📌 결론
트리 순회는 정해진 순서에 따라 노드를 방문하는 기본적인 알고리즘입니다.
같은 트리라도 어떤 순회 방식을 사용하는지에 따라 방문 순서가 달라집니다.
정리해 보면 다음과 같습니다.
- 이진 트리는 각 노드가 최대 두 개의 자식을 가지는 트리입니다.
- 전위 순회는 부모 → 왼쪽 → 오른쪽 순서입니다.
- 중위 순회는 왼쪽 → 부모 → 오른쪽 순서입니다.
- 후위 순회는 왼쪽 → 오른쪽 → 부모 순서입니다.
- 세 순회 방식은 트리 문제의 가장 기본이 되는 개념입니다.
트리 순회는 단순히 출력 순서만 외우는 것이 아니라,
부모를 언제 처리하는가를 기준으로 이해하면 훨씬 오래 기억할 수 있습니다.
PS 문제를 풀 때도 순회 방식을 정확히 구분할 수 있어야 적절한 코드를 작성할 수 있습니다.
