13 — 트리 구조

람다가 가족 나무(가계도)를 들여다보며 "맨 위에 한 명, 그 아래로 갈라지면서 점점 늘어나네?"라고 발견하고, 제네릭이 운동회 토너먼트 대진표를 펼쳐 보이며 "이것도 위에서 갈라져 내려와!"라고 거들자, 돌핀쌤이 "맞아요, 위에서 아래로 가지치는 그 구조가 바로 트리예요"라고 안내하는 도입

🙋‍♀️ 람다: "가족 나무를 봤는데, 맨 위에 할아버지 한 명이 있고 아래로 내려갈수록 갈라지면서 사람이 늘어나요!"

🙋‍♂️ 제네릭: "운동회 토너먼트 대진표도 똑같아! 우승자 한 자리에서 아래로 갈라지면서 선수들이 늘어나잖아."

🐬 돌핀쌤: "두 친구가 발견한 그 구조가 바로 오늘 배울 트리예요. 위에서 아래로 가지를 치며 뻗어 나가는 구조랍니다."

🎯 오늘 완성할 코드는?

오늘 우리가 만들 건 트리를 코드로 표현하기예요. 위에서 아래로 갈라지는 트리 모양을, 딕셔너리로 적어 두고 "누구의 자식이 누구인지" 꺼내 보는 코드예요.

먼저 완성된 모습부터 볼게요. 지금은 이해 안 돼도 괜찮아요. 아래에서 한 줄씩 천천히 뜯어볼 거예요.

tree = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': [],
    'F': [],
}
print(tree['A'])   # ['B', 'C'] — A의 자식들
print(tree['B'])   # ['D', 'E'] — B의 자식들

실행하면 이렇게 나와요.

['B', 'C']
['D', 'E']

A 의 자식이 B, C 이고, B 의 자식이 D, E 라는 게 그대로 출력됐죠?

🐬 돌핀쌤: "짧은 코드지만, 이 안에 트리의 핵심이 다 들어 있어요. '누가 누구의 자식인지'만 적어 두면 그게 바로 트리거든요. 지금부터 이 코드가 왜 트리를 표현하는지 하나씩 풀어볼게요."

💡 어떻게 풀까? — 위에서 아래로 가지치는 구조

우리 주변엔 트리 구조가 정말 많아요. 맨 위에 하나가 있고, 아래로 갈라지면서 뻗어 나가는 모양이라면 전부 트리예요.

가족 나무

           할아버지
          /        \
       아버지       삼촌
       /    \
    나(장남)  동생

컴퓨터 폴더

C드라이브
├── 문서
│   ├── 학교숙제
│   └── 일기
└── 사진
    ├── 2023
    └── 2024

람다가 발견한 가족 나무, 제네릭이 보여 준 토너먼트 대진표가 모두 트리였던 거예요.

그럼 이 모양을 코드로 어떻게 적을까요? 비결은 간단해요. "누구의 자식이 누구인지"만 적어 두면 돼요. 맨 위 코드의 'A': ['B', 'C'] 가 바로 "A의 자식은 B와 C" 라는 뜻이에요.

🙋‍♀️ 람다: "그림으로 그린 가지를, 글로 '누구의 자식은 누구' 라고 받아 적은 거네요!"

🔍 코드 한 줄씩 뜯어보기

이제 맨 위에서 본 완성 코드를 한 줄씩 볼게요. 먼저 우리가 표현할 트리는 이렇게 생겼어요.

          [A]        ← 루트 (맨 위 노드)
         /   \
       [B]   [C]
       / \     \
     [D] [E]  [F]    ← 리프 (자식 없는 끝 노드)

① 트리를 딕셔너리로 적어요

tree = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': [],
    'F': [],
}

tree 는 딕셔너리예요. 화살표 왼쪽('A')은 노드 이름(열쇠), 오른쪽(['B', 'C'])은 그 노드의 자식 목록이에요. 그러니까 'A': ['B', 'C'] 는 "A의 자식은 B와 C" 라는 뜻이에요.

💡 'D': [] 처럼 빈 목록([])은 자식이 없다는 뜻이에요. 자식이 없는 끝 노드를 리프(leaf) 라고 불러요. 위 그림에서 D, E, F가 리프예요.

② 자식을 꺼내 봐요

print(tree['A'])   # ['B', 'C'] — A의 자식들
print(tree['B'])   # ['D', 'E'] — B의 자식들

tree['A'] 라고 쓰면 A의 자식 목록(['B', 'C'])이 그대로 나와요. 딕셔너리에서 열쇠를 넣으면 그 값을 꺼내는 것과 똑같아요. 트리에서 "이 노드의 자식이 누구지?" 를 알고 싶을 때 이렇게 꺼내 봐요.

③ 트리 용어 정리

코드를 읽으려면 부르는 이름을 알아야 해요. 위 그림과 코드를 같이 보면서 익혀요.

용어	설명	예시
노드 (Node)	트리의 각 칸	A, B, C, D, E, F
루트 (Root)	가장 위의 노드	A
부모 (Parent)	바로 위 노드	B의 부모는 A
자식 (Child)	바로 아래 노드	A의 자식은 B, C
형제 (Sibling)	같은 부모를 둔 노드	B와 C는 형제
리프 (Leaf)	자식이 없는 노드	D, E, F
깊이 (Depth)	루트에서 그 노드까지 거리	A=0, B=1, D=2
높이 (Height)	루트에서 가장 깊은 리프까지 거리	이 트리는 2

🙋‍♂️ 제네릭: "딕셔너리의 열쇠가 노드, 값이 그 노드의 자식 목록이군요. [] 면 리프고요!"

✍️ 직접 완성해보기

이제 빈칸을 채워 직접 완성해봐요. 위에서 본 그대로예요.

tree = {
    'A': [___, ___],     # A의 자식은 B, C
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': [],
    'F': [],
}
print(tree[___])   # A의 자식들 → ['B', 'C']
print(tree['B'])   # ['D', 'E'] — B의 자식들

🐬 돌핀쌤: "막히면 위 '코드 한 줄씩 뜯어보기'로 다시 올라가서 확인해요. 다 채웠으면 맨 위 🎯 완성 코드와 비교해보세요. 정답을 외우는 게 아니라 왜 그런지 떠올리는 게 진짜 공부예요."

📌 오늘 배운 것

개념	설명
트리	위에서 아래로 가지치며 뻗어 나가는 구조 (가족 나무, 폴더, 토너먼트)
노드 · 루트 · 리프	각 칸이 노드, 맨 위가 루트, 자식 없는 끝이 리프
부모 · 자식	바로 위가 부모, 바로 아래가 자식
딕셔너리로 표현	`'노드': [자식들]` — 노드를 열쇠, 자식 목록을 값으로
자식 꺼내기	`tree['A']` 처럼 노드 이름을 넣으면 자식 목록이 나옴

🐬 돌핀쌤: "노드, 루트, 리프, 그리고 '누구의 자식은 누구'! 이것만 알면 어떤 트리든 코드로 적을 수 있어요. 잘했어요! 👏"

▸ 더 해보기 — 여기서부터는 선택!

여기까지가 오늘의 필수 내용이에요. 아래는 여유 있을 때 도전하는 내용이고, 예제 문제로 직접 풀어볼 수 있어요. 외울 필요는 없어요.

이진 트리 — 자식을 최대 2개(왼쪽·오른쪽)까지만 가지는 트리예요. 자료구조에서 가장 많이 쓰이고, 나중에 배울 힙도 이진 트리예요. → 예제로 연습
완전 이진 트리 — 위에서, 그리고 왼쪽부터 빈틈없이 채운 이진 트리예요. 왼쪽이 비었는데 오른쪽에만 자식이 있으면 완전 이진 트리가 아니에요. → 예제로 연습
Node 클래스로 트리 만들기 — 딕셔너리 대신 class Node(value·left·right)로 노드를 찍어내고 root.left = Node(5) 처럼 이어 붙여요. → 예제로 연습
트리 높이 계산 (재귀) — 지난 시간에 배운 재귀로 트리의 높이를 구해요. "현재 노드에서 할 일을 하고, 왼쪽·오른쪽 자식에게 같은 일을 시킨다"가 핵심이에요. → 예제로 연습
노드 개수 세기 (재귀) — 높이 계산과 똑같은 틀로, 노드가 몇 개인지 세요. → 예제로 연습

🐬 돌핀쌤: "기본을 완벽히 익힌 다음 도전하세요. 전부 '트리는 노드 아래에 또 트리'라는 같은 생각 위에 살을 붙인 거예요."

참고 — 트리 재귀의 약속

돌핀쌤이 칠판 앞에서 지느러미로 손가락을 펴며 트리의 핵심(① 루트에서 아래로 가지치는 구조 ② 노드는 값·자식을 가짐 ③ 트리 재귀는 첫 줄에 None 체크)을 정리하고 람다·제네릭이 끄덕이는 장면

위 '더 해보기'의 높이·개수 세기처럼 트리를 재귀로 다룰 때는 꼭 지킬 약속이 하나 있어요.

def height(node):
    if node is None:    # ← 빈 자리에 닿으면 멈추기 (반드시 첫 줄에!)
        return -1
    return 1 + max(height(node.left), height(node.right))

자식이 없는 자리(None)에 닿으면 멈춰야 하거든요. 이 종료 조건을 빠뜨리면 끝없이 아래로 내려가다 멈추지 않아요. 트리 재귀 함수는 항상 첫 줄에 if node is None: 체크를 먼저 두세요.

13 — 트리 구조

📃 해결할 문제

💻 예제 입력 1

🖨️ 예제 출력 1