10강 / 20강

트리 — 뿌리에서 뻗어 나가는 가지

계층을 담는 그릇, 그리고 세 가지 순회

지금까지의 자료구조는 전부 한 줄이었습니다. 리스트도, 스택도, 큐도, 연결 리스트도요. 그런데 세상에는 한 줄로 표현할 수 없는 것들이 있습니다.

폴더 안에 폴더, 그 안에 또 폴더 📁
회사 조직도 — 사장 밑에 부장, 부장 밑에 팀원
가계도, 토너먼트 대진표, 웹페이지의 HTML 구조

이런 계층 구조를 담는 그릇이 트리(tree)입니다. 8강의 연결 리스트가 "다음 하나"를 가리켰다면, 트리는 "자식 여럿"을 가리킵니다.

용어	뜻
노드(node)	동그라미 하나. 값이 들어 있는 자리
루트(root)	맨 위 노드. 부모가 없는 단 하나
부모 / 자식	바로 위 / 바로 아래로 이어진 노드
잎(leaf)	자식이 없는 노드. 가지 끝
깊이 / 높이	루트에서 몇 칸 아래인가 / 트리 전체가 몇 층인가

고등학생계층을 담는 그릇

8강의 연결 리스트가 "다음 하나" 를 가리켰다면, 트리는 "자식 여럿" 을 가리킵니다.

화살표를 여러 개 두면 줄이 가지가 된다

용어부터

말	뜻
루트	맨 위 — 시작점
부모 · 자식	위 · 아래
잎(leaf)	자식이 없는 것
깊이	루트에서 몇 단계

나무를 거꾸로 그린다 — 뿌리가 위

왜 거꾸로 그리나

글은 위에서 아래로 읽으니까요. 시작점을 위에 두는 게 자연스럽습니다.

일상에 트리가 널려 있습니다

것	부모-자식
폴더	폴더 안의 폴더
조직도	부서 안의 팀
HTML	태그 안의 태그
가계도	말 그대로
목차	장 안의 절

"안에 들어 있다" 는 관계는 전부 트리다

왜 이 모양이 유용한가

깊이가 log 로 자라기 때문입니다.

노드 수	깊이 (자식 2개일 때)
7	3
1,000	10
1,000,000	20

100만 개인데 20단계 — 11강의 폭발적 검색 속도의 뿌리

트리를 다루는 코드에는 재귀가 거의 항상 등장합니다.

Python 브라우저에서 실행

# 딕셔너리로 트리 만들기 — 폴더 구조
파일들 = {
    "내문서": {
        "사진": {"제주도.jpg": None, "졸업식.jpg": None},
        "숙제": {"자료구조": {"1강.py": None, "2강.py": None}},
        "메모.txt": None,
    }
}

def 그리기(가지, 깊이=0):
    for 이름, 안쪽 in 가지.items():
        print("    " * 깊이 + ("📁 " if 안쪽 else "📄 ") + 이름)
        if 안쪽:
            그리기(안쪽, 깊이 + 1)     # 재귀! (9강)

그리기(파일들)

고등학생트리와 재귀는 한 몸입니다

note 의 이 문장이 9강을 먼저 배운 이유입니다.

트리의 가지도 트리다 — 그래서 재귀가 딱 맞는다

이 성질이 핵심입니다

노드 하나를 떼어 내면 그것도 완전한 트리예요. 이걸 서브트리라 합니다.

구조	부분도 같은 구조인가
리스트의 일부	리스트 ✔
트리의 가지	트리 ✔

9강의 조건 — "똑같은데 작은 문제" 가 저절로 생긴다

그래서 트리 코드가 이렇게 짧습니다

def 개수(node):
    if node is None:
        return 0
    return 1 + 개수(node.왼쪽) + 개수(node.오른쪽)

세 줄입니다. 반복문으로 쓰면 훨씬 길어요.

"나 하나 + 왼쪽에게 맡기기 + 오른쪽에게 맡기기"

깊이도 같은 방식

def 깊이(node):
    if node is None:
        return 0
    return 1 + max(깊이(node.왼쪽), 깊이(node.오른쪽))

패턴이 똑같다 — 합치는 방법만 다르다

비유 — 조직도에서 인원 세기

사장이 전체 인원을 알고 싶습니다. 직접 다 셀까요?

방법	비유
직접 센다	반복문 — 복잡하다
각 부장에게 묻는다	재귀 — 자기 부서를 세서 보고

부장도 과장들에게 묻습니다. 과장도 마찬가지고요.

각자 "내 밑" 만 세면 전체가 세어진다

이진 트리 — 자식이 최대 둘

자식을 왼쪽·오른쪽 둘까지만 두기로 약속한 트리를 이진 트리(binary tree)라고 합니다. 규칙을 좁히면 다루기가 훨씬 쉬워지고, 11강에서는 여기에 규칙을 하나 더 얹어 엄청나게 빠른 검색을 만들어 냅니다.

재귀 세 줄이면 트리의 높이도 개수도 구해집니다.

Python 브라우저에서 실행

class 노드:
    def __init__(self, 값, 왼=None, 오=None):
        self.값, self.왼, self.오 = 값, 왼, 오

#         1
#       /   \
#      2     3
#     / \
#    4   5
뿌리 = 노드(1, 노드(2, 노드(4), 노드(5)), 노드(3))

def 높이(ㄴ):
    if ㄴ is None:
        return 0
    return 1 + max(높이(ㄴ.왼), 높이(ㄴ.오))

def 개수(ㄴ):
    if ㄴ is None:
        return 0
    return 1 + 개수(ㄴ.왼) + 개수(ㄴ.오)

print("높이:", 높이(뿌리))
print("노드 수:", 개수(뿌리))

🎮 트리를 만들고 순회해 보세요

트리는 한 줄이 아니라서 "어떤 순서로 다 방문할 것인가"가 문제가 됩니다. 이걸 순회(traversal)라고 하고, 방법이 세 가지 있어요. 아래에서 각각을 눌러 애니메이션으로 확인해 보세요.

고등학생세 가지 순회

트리를 전부 훑는 방법이 세 가지 있습니다. 그런데 차이는 한 줄의 위치 뿐이에요.

이름	순서	언제 쓰나
전위	나 → 왼 → 오	구조를 복사할 때
중위	왼 → 나 → 오	정렬된 순서 (11강)
후위	왼 → 오 → 나	지울 때 · 계산할 때

print 를 어디에 두느냐 만 다르다

왜 이렇게 나뉘나 — 쓰임이 다르다

전위 — 폴더 구조를 복사할 때 부모 폴더를 먼저 만들어야 하죠.

부모가 있어야 자식을 넣는다

후위 — 폴더를 지울 때는 반대입니다. 안의 것을 먼저 지워야 해요.

자식이 없어야 부모를 지울 수 있다

비유 — 짐 싸기와 풀기

일	순서	순회
상자에 담기	큰 상자를 먼저 펴고	전위
정리하기	안의 것을 먼저 꺼내고	후위

만들 때와 없앨 때가 정확히 반대 순서다

중위가 특별한 이유

일반 트리에서는 별 뜻이 없습니다. 그런데 이진 탐색 트리에서는 —

중위 순회 = 완벽하게 정렬된 순서 (11강)

이게 놀라운 성질이에요. 정렬하려고 한 게 아닌데 정렬되어 나옵니다.

세 가지 순회 — 나를 언제 방문하느냐의 차이

왼쪽 가지·나·오른쪽 가지, 이 셋을 어떤 순서로 처리하느냐만 다릅니다.

이름	순서	쓰이는 곳
전위 (preorder)	나 → 왼 → 오	트리 복사, 폴더 구조 출력
중위 (inorder)	왼 → 나 → 오	이진탐색트리를 정렬된 순서로 (11강)
후위 (postorder)	왼 → 오 → 나	폴더 용량 계산, 트리 삭제
레벨 (BFS)	위층부터 한 층씩	가까운 것부터 찾기 (15강)

세 줄짜리 순회 세 개. print 위치만 다릅니다.

Python 브라우저에서 실행

class 노드:
    def __init__(self, 값, 왼=None, 오=None):
        self.값, self.왼, self.오 = 값, 왼, 오

뿌리 = 노드(1, 노드(2, 노드(4), 노드(5)), 노드(3, 노드(6)))

def 전위(ㄴ):
    if ㄴ: print(ㄴ.값, end=" "); 전위(ㄴ.왼); 전위(ㄴ.오)
def 중위(ㄴ):
    if ㄴ: 중위(ㄴ.왼); print(ㄴ.값, end=" "); 중위(ㄴ.오)
def 후위(ㄴ):
    if ㄴ: 후위(ㄴ.왼); 후위(ㄴ.오); print(ㄴ.값, end=" ")

print("전위:", end=" "); 전위(뿌리); print()
print("중위:", end=" "); 중위(뿌리); print()
print("후위:", end=" "); 후위(뿌리); print()

# 레벨 순회는 재귀가 아니라 '큐'로 합니다 (7강!)
from collections import deque
def 레벨(뿌리):
    ㄷ = deque([뿌리])
    while ㄷ:
        ㄴ = ㄷ.popleft()
        print(ㄴ.값, end=" ")
        if ㄴ.왼: ㄷ.append(ㄴ.왼)
        if ㄴ.오: ㄷ.append(ㄴ.오)
print("레벨:", end=" "); 레벨(뿌리); print()

고등학생print 자리만 옮기면 됩니다

note 가 강조한 한 줄의 위치를 직접 봅시다.

def 전위(n):
    if not n: return
    print(n.값)      # ← 여기
    전위(n.왼); 전위(n.오)

def 중위(n):
    if not n: return
    중위(n.왼)
    print(n.값)      # ← 여기
    중위(n.오)

def 후위(n):
    if not n: return
    후위(n.왼); 후위(n.오)
    print(n.값)      # ← 여기

구조는 똑같고 한 줄이 어디 있느냐 만 다르다

이걸 아는 게 왜 중요한가

재귀의 세 순간을 구별하게 되기 때문입니다.

순간	무엇을 아는가
들어갈 때	나 자신 — 아래는 모른다
중간	왼쪽 결과를 안다
나올 때	아래 전부를 안다

"아래의 결과가 필요하면" 후위에서 처리한다

실전 예 — 폴더 크기 계산

def 크기(폴더):
    합 = 0
    for 자식 in 폴더.자식들:
        합 += 크기(자식)     # 아래를 먼저
    합 += 폴더.자기크기
    return 합                # ← 후위

아래 크기를 알아야 내 크기를 안다 — 그래서 후위

비유 — 성적 집계

일	순서
반 평균	학생 점수를 먼저
학년 평균	반 평균을 먼저
학교 평균	학년 평균을 먼저

아래가 끝나야 위를 계산한다 — 후위 순회의 전형

반대로 "공지 전달" 은 전위입니다. 위에서 아래로 퍼지니까요.

정보가 어느 방향으로 흐르냐가 순회를 정한다

계산기와 컴파일러가 수식을 이해하는 방식입니다.

Python 브라우저에서 실행

# 트리로 수식 계산하기 — (3 + 5) × 2
class 노드:
    def __init__(self, 값, 왼=None, 오=None):
        self.값, self.왼, self.오 = 값, 왼, 오

식 = 노드("×", 노드("+", 노드(3), 노드(5)), 노드(2))

def 계산(ㄴ):
    if ㄴ.왼 is None:              # 잎 = 숫자
        return ㄴ.값
    ㄱ, ㄴ2 = 계산(ㄴ.왼), 계산(ㄴ.오)   # 후위 순회!
    return {"+": ㄱ+ㄴ2, "-": ㄱ-ㄴ2, "×": ㄱ*ㄴ2, "÷": ㄱ/ㄴ2}[ㄴ.값]

print("(3 + 5) × 2 =", 계산(식))

🤔 확인 문제

트리에서 루트(root)는?

🤔 확인 문제

트리를 다루는 코드에 재귀가 자주 나오는 이유는?

🤔 확인 문제

레벨 순회(위층부터 한 층씩)를 구현할 때 필요한 자료구조는?