코틀린 코딩테스트 강좌, 트리 순회하기

오늘의 주제는 트리 순회(Tree Traversal)입니다. 트리는 데이터 구조 중 하나로, 특정한 관계를 가진 요소들이 계층적으로 구성되어 있습니다. 우리가 자주 사용하는 데이터 구조 중 하나인 트리를 이해하고, 기본적인 순회 알고리즘을 구현하는 것은 코딩 테스트에서 매우 유용합니다. 이 글에서는 트리의 기본 개념부터 시작하여, 다양한 순회 방법과 코틀린에서의 구현 방법에 대해 알아보겠습니다.

1. 트리의 기본 개념

트리는 노드(Node)로 구성된 데이터 구조입니다. 각 노드는 값과 자식 노드를 가질 수 있습니다. 트리는 다음과 같은 주요 용어로 설명할 수 있습니다:

  • 루트 노드 (Root Node): 트리의 최상위 노드입니다.
  • 리프 노드 (Leaf Node): 자식 노드가 없는 노드입니다.
  • 내부 노드 (Internal Node): 자식 노드를 가진 노드입니다.
  • 서브트리 (Subtree): 특정 노드를 루트로 하는 트리입니다.

2. 트리 순회의 종류

트리를 순회하는 방법은 크게 세 가지로 나눌 수 있습니다:

  1. 전위 순회 (Pre-order Traversal): 노드 방문 – 왼쪽 서브트리 순회 – 오른쪽 서브트리 순회
  2. 중위 순회 (In-order Traversal): 왼쪽 서브트리 순회 – 노드 방문 – 오른쪽 서브트리 순회
  3. 후위 순회 (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. 추가 연습 문제

아래의 문제를 풀어보며 트리 순회에 대한 이해도를 높여보세요:

  1. 주어진 이진 트리의 깊이를 계산하는 함수를 작성하시오.
  2. 이진 트리의 최대 경로 합을 찾는 함수를 작성하시오.

9. 결론

이제 트리 구조와 순회 방법에 대한 기본적인 이해를 갖추었으므로, 더 복잡한 코딩문제에도 도전할 준비가 되셨을 것입니다. 트리가 활용되는 다양한 알고리즘 문제들을 풀면서, 이 부분에 대한 실력을 더욱 쌓아보시기 바랍니다. 다음 강좌에서는 그래프 탐색에 대해 다루어 보겠습니다. 감사합니다!

Copyright © 2023 – 코딩테스트 강좌