자바 코딩테스트 강좌, 트리 순회하기

트리(Tree)는 컴퓨터 과학에서 중요한 자료구조 중 하나입니다. 특히, 이진 트리(Binary Tree)는 많은 알고리즘 문제에서 기본적으로 사용되며, 특히 검색 및 정렬 작업에 유용합니다. 이 강좌에서는 이진 트리의 기본 구성 요소 및 트리 순회의 여러 방법들(전위, 중위, 후위 순회)을 다룰 것입니다. 또한, 이를 바탕으로 트리 순회를 구현하는 문제를 하나 준비했습니다.

트리 개념 및 구조

트리는 노드(Node)들로 구성된 비선형 자료구조입니다. 트리의 각 노드는 자식 노드를 가질 수 있으며, 이러한 자식 노드는 다시 노드를 가질 수 있습니다. 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리입니다. 트리의 기본 요소는 다음과 같습니다:

  • 루트 노드(Root Node): 트리의 최상위 노드입니다.
  • 리프 노드(Leaf Node): 자식 노드가 없는 노드입니다.
  • 부모 노드(Parent Node): 다른 노드의 자식 노드인 노드입니다.
  • 자식 노드(Child Node): 부모 노드에 의해 연결된 노드입니다.

트리 순회 개요

트리 순회(Traversal)는 트리의 모든 노드를 방문하는 과정을 의미합니다. 트리 순회의 방법은 다음과 같습니다:

1. 전위 순회(Pre-order Traversal)

전위 순회는 각 노드를 방문할 때 부모 노드를 먼저 방문한 후 자식 노드를 방문하는 방식입니다. 순서로는 다음과 같습니다:

  1. 현재 노드 방문
  2. 왼쪽 서브트리 순회
  3. 오른쪽 서브트리 순회

2. 중위 순회(In-order Traversal)

중위 순회는 왼쪽 서브트리를 먼저 순회한 후 현재 노드를 방문하고, 마지막으로 오른쪽 서브트리를 방문하는 방식입니다. 순서로는 다음과 같습니다:

  1. 왼쪽 서브트리 순회
  2. 현재 노드 방문
  3. 오른쪽 서브트리 순회

3. 후위 순회(Post-order Traversal)

후위 순회는 모든 자식 노드를 방문한 후 마지막에 부모 노드를 방문하는 방식입니다. 순서로는 다음과 같습니다:

  1. 왼쪽 서브트리 순회
  2. 오른쪽 서브트리 순회
  3. 현재 노드 방문

문제 제시

이제 트리 순회 알고리즘을 실습할 문제를 소개하겠습니다:

문제: 이진 트리의 전위 순회 출력하기

이진 트리의 루트 노드가 주어졌을 때, 전위 순회 방식으로 모든 노드를 방문하여 방문 순서를 출력하는 메소드를 작성하시오. 단, 노드는 TreeNode 클래스를 사용하여 정의할 수 있습니다.

문제 풀이

1. TreeNode 클래스 정의

이진 트리를 구성하기 위한 TreeNode 클래스를 정의합니다. 이 클래스는 노드의 데이터와 왼쪽 및 오른쪽 자식 노드를 포함합니다.

class TreeNode {
        int data;
        TreeNode left;
        TreeNode right;

        TreeNode(int data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }

2. 전위 순회 메소드 구현

전위 순회를 위한 메소드를 구현합니다. 이 방법은 재귀적으로 정의됩니다.

public void preOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        // 현재 노드 방문
        System.out.print(node.data + " ");
        // 왼쪽 서브트리 순회
        preOrder(node.left);
        // 오른쪽 서브트리 순회
        preOrder(node.right);
    }

3. 테스트

구현한 전위 순회 메소드를 테스트하기 위해 트리를 생성하고 결과를 출력합니다.

public class Main {
        public static void main(String[] args) {
            TreeNode root = new TreeNode(1);
            root.left = new TreeNode(2);
            root.right = new TreeNode(3);
            root.left.left = new TreeNode(4);
            root.left.right = new TreeNode(5);

            Main main = new Main();
            System.out.print("전위 순회 결과: ");
            main.preOrder(root); // 예상 결과: 1 2 4 5 3
        }
    }

결과 확인

이를 실행하면 다음과 같은 전위 순회 결과를 얻을 수 있습니다:

전위 순회 결과: 1 2 4 5 3

최적화와 심화 학습

이진 트리의 순회 방법에 대한 이해를 바탕으로, 데이터 트리에서 복잡한 탐색 또는 정렬 알고리즘에서의 응용을 심화 학습할 수 있습니다. 예를 들어, 중위 순회를 통해 이진 탐색 트리(BST)의 노드들을 오름차순으로 출력하는 방법을 익힐 수 있습니다.

팁: 트리 순회 방법을 이해하는 것은 알고리즘 인터뷰에서도 중요한 포인트입니다. 다양한 트리 순회 문제를 풀어보며 실력을 키우는 것이 좋습니다.

마무리

이번 강좌에서는 이진 트리의 기본 개념과 함께 전위 순회 알고리즘을 구현해보았습니다. 트리 순회는 알고리즘 문제와 실무에서도 자주 등장하는 중요한 주제이므로, 다양한 방법을 연습하며 자신만의 코드 스타일을 개발하는 것이 좋습니다. 앞으로도 다른 순회 방법과 문제들에 대해서도 지속적으로 학습해 나가기를 바랍니다.