오늘의 주제는 트리 순회(Tree Traversal)입니다. 트리는 데이터 구조 중 하나로, 특정한 관계를 가진 요소들이 계층적으로 구성되어 있습니다. 우리가 자주 사용하는 데이터 구조 중 하나인 트리를 이해하고, 기본적인 순회 알고리즘을 구현하는 것은 코딩 테스트에서 매우 유용합니다. 이 글에서는 트리의 기본 개념부터 시작하여, 다양한 순회 방법과 코틀린에서의 구현 방법에 대해 알아보겠습니다.
1. 트리의 기본 개념
트리는 노드(Node)로 구성된 데이터 구조입니다. 각 노드는 값과 자식 노드를 가질 수 있습니다. 트리는 다음과 같은 주요 용어로 설명할 수 있습니다:
- 루트 노드 (Root Node): 트리의 최상위 노드입니다.
- 리프 노드 (Leaf Node): 자식 노드가 없는 노드입니다.
- 내부 노드 (Internal Node): 자식 노드를 가진 노드입니다.
- 서브트리 (Subtree): 특정 노드를 루트로 하는 트리입니다.
2. 트리 순회의 종류
트리를 순회하는 방법은 크게 세 가지로 나눌 수 있습니다:
- 전위 순회 (Pre-order Traversal): 노드 방문 – 왼쪽 서브트리 순회 – 오른쪽 서브트리 순회
- 중위 순회 (In-order Traversal): 왼쪽 서브트리 순회 – 노드 방문 – 오른쪽 서브트리 순회
- 후위 순회 (Post-order Traversal): 왼쪽 서브트리 순회 – 오른쪽 서브트리 순회 – 노드 방문
3. 문제 설명
다음과 같은 이진 트리가 주어진다고 가정합시다:
1
/ \
2 3
/ \ / \
4 5 6 7
이 트리에서 전위 순회, 중위 순회 및 후위 순회의 결과를 각각 나열하십시오.
4. 문제 해결 과정
이 문제를 해결하기 위해 가장 먼저 필요로 하는 것은 트리에 대한 클래스 구조를 정의하는 것입니다. 코틀린에서는 다음과 같이 이진 트리의 노드를 클래스 형태로 구현할 수 있습니다:
4.1) 이진 트리 노드 클래스 정의
class TreeNode(val value: Int) {
var left: TreeNode? = null
var right: TreeNode? = null
}위 클래스는 노드의 값을 저장하는 value와 왼쪽과 오른쪽 자식 노드를 참조하는 left, right 변수를 가집니다.
4.2) 전위 순회 구현
전위 순회는 노드를 방문한 후 자식 노드를 방문하는 방식입니다. 이를 위한 함수는 다음과 같습니다:
fun preOrderTraversal(node: TreeNode?) {
if (node == null) return
print("${node.value} ")
preOrderTraversal(node.left)
preOrderTraversal(node.right)
}4.3) 중위 순회 구현
중위 순회는 왼쪽 자식을 먼저 방문한 후 현재 노드를 방문하는 방식입니다. 다음과 같이 구현할 수 있습니다:
fun inOrderTraversal(node: TreeNode?) {
if (node == null) return
inOrderTraversal(node.left)
print("${node.value} ")
inOrderTraversal(node.right)
}4.4) 후위 순회 구현
후위 순회는 양쪽 자식을 방문한 후 현재 노드를 방문하는 방식입니다. 구현은 다음과 같습니다:
fun postOrderTraversal(node: TreeNode?) {
if (node == null) return
postOrderTraversal(node.left)
postOrderTraversal(node.right)
print("${node.value} ")
}5. 트리 생성 및 테스트
이제 실제로 트리를 생성하고, 각 순회 방법을 테스트해보겠습니다. 다음과 같은 코드로 트리를 구성하고 순회를 실행할 수 있습니다:
fun main() {
val root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left?.left = TreeNode(4)
root.left?.right = TreeNode(5)
root.right?.left = TreeNode(6)
root.right?.right = TreeNode(7)
print("전위 순회: ")
preOrderTraversal(root)
println()
print("중위 순회: ")
inOrderTraversal(root)
println()
print("후위 순회: ")
postOrderTraversal(root)
println()
}6. 코드 실행 결과
위의 프로그램을 실행하면 다음과 같은 결과를 얻을 수 있습니다:
전위 순회: 1 2 4 5 3 6 7
중위 순회: 4 2 5 1 6 3 7
후위 순회: 4 5 2 6 7 3 1
7. 요약
이번 글에서는 트리에 대한 기본 개념과 트리 순회의 세 가지 방법인 전위 순회, 중위 순회, 그리고 후위 순회에 대해 알아보았습니다. 각각의 순회 방법을 코틀린으로 구현하고, 실전에서도 사용할 수 있는 간단한 예제를 통해 트리 구조를 이해할 수 있었습니다. 코딩 테스트에서 자주 접하게 될 트리 문제이므로, 충분히 연습하여 익숙해지는 것이 중요합니다.
8. 추가 연습 문제
아래의 문제를 풀어보며 트리 순회에 대한 이해도를 높여보세요:
- 주어진 이진 트리의 깊이를 계산하는 함수를 작성하시오.
- 이진 트리의 최대 경로 합을 찾는 함수를 작성하시오.
9. 결론
이제 트리 구조와 순회 방법에 대한 기본적인 이해를 갖추었으므로, 더 복잡한 코딩문제에도 도전할 준비가 되셨을 것입니다. 트리가 활용되는 다양한 알고리즘 문제들을 풀면서, 이 부분에 대한 실력을 더욱 쌓아보시기 바랍니다. 다음 강좌에서는 그래프 탐색에 대해 다루어 보겠습니다. 감사합니다!