자료구조 · 알고리즘 기초집LESSON 16

트리 기초: 계층 구조와 순회 방법

난이도초급 → 중급 입문

예상 시간40분

선수지식이전 강의

16강. 트리 기초: 계층 구조와 순회 방법

1. 이번 강의에서 해결할 문제

게임의 월드·지역·스테이지처럼 계층 관계가 있는 데이터를 평평한 목록만으로 표현하면 부모와 하위 구조를 반복해서 찾게 됩니다.

2. 학습 목표

3. 핵심 개념

트리는 연결된 계층 구조로, 루트는 부모가 없고 리프는 자식이 없습니다. 이진 트리는 각 노드의 자식이 최대 둘입니다. 전위는 노드-왼쪽-오른쪽이라 구조 복사, 중위는 왼쪽-노드-오른쪽이라 이진 탐색 트리의 정렬 출력, 후위는 자식-노드라 하위 자원 정리에 어울립니다. 일반 트리와 이진 탐색 트리는 같은 개념이 아닙니다.

4. 단계별 실습

1. 예제 파일 작성

실행 환경: 코드 편집기

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: 같은 이름의 파일이 있다면 덮어쓰기 전에 Git diff로 변경 범위를 확인합니다. 선택한 LTS JDK의 java -version과 javac -version이 모두 실행되어야 합니다.

대상 파일: src/StageTreeTraversal.java

src/StageTreeTraversal.java
public class StageTreeTraversal {
    static final class Node {
        String name;
        Node left, right;
        Node(String name) { this.name = name; }
    }
    static void preorder(Node node) {
        if (node == null) return;
        System.out.print(node.name + " ");
        preorder(node.left);
        preorder(node.right);
    }
    static void inorder(Node node) {
        if (node == null) return;
        inorder(node.left);
        System.out.print(node.name + " ");
        inorder(node.right);
    }

    public static void main(String[] args) {
        Node root = new Node("World");
        root.left = new Node("Forest");
        root.right = new Node("Castle");
        root.left.left = new Node("Cave");
        preorder(root); System.out.println();
        inorder(root); System.out.println();
    }
}

2. PowerShell에서 컴파일·실행

실행 환경: Windows PowerShell

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: src/StageTreeTraversal.java가 저장되었고 out 폴더에는 삭제해도 되는 컴파일 결과만 있는지 확인합니다.

대상: src/StageTreeTraversal.java와 out 아래 생성되는 class 파일

Windows PowerShell
Set-Location C:\dev\game-ranking-algorithms
New-Item -ItemType Directory -Force .\out | Out-Null
javac -Xlint:all -d .\out .\src\StageTreeTraversal.java
java -cp .\out StageTreeTraversal

예상 결과: 전위는 World Forest Cave Castle, 중위는 Cave Forest World Castle 순으로 출력됩니다.

실행 시간은 PC의 CPU·메모리, JDK 버전, JVM 워밍업, 백그라운드 작업과 입력 분포에 따라 달라질 수 있습니다. 측정값은 같은 조건에서 여러 번 비교하고 Big-O 분석과 함께 해석합니다.

5. 코드와 알고리즘이 동작하는 이유

각 순회는 모든 노드를 한 번 방문해 O(n) 시간입니다. 재귀 깊이는 트리 높이 h와 같아 O(h) 공간이며, 균형 트리는 O(log n), 한쪽으로 치우친 트리는 O(n)까지 커집니다.

6. 자주 하는 실수와 해결법

7. 직접 실습

8. 이해 점검 질문 3개

9. 핵심 요약

MINI QUIZ