2. 트리(Tree) | III단원

🎮 이 단원이 게임에서 쓰이는 곳 (언더테일·RPG)

트리 = 스토리 분기를 나타낼 때 씁니다. 루트가 "시작 장면", 자식이 "선택지별 다음 장면", 리프가 "엔딩·막다른 장면"이에요. 파피루스에게 말을 걸지 말지 같은 선택지가 2개면 이진 트리, 3개면 자식이 3개인 노드로 확장할 수 있어요. 퀘스트 의존 관계도 트리로 표현할 수 있습니다.

트리(Tree, 트리)

트리는 맨 위에서부터 아래로 뻗어 나가는 구조예요. 한 지점에서 여러 개가 갈라질 수 있어요. 사이클(돌고 도는 연결)이 없어요.

용어

루트(root, 루트): 맨 위의 시작점. 나무 뿌리처럼.
부모 / 자식: 위에 있는 게 부모, 바로 아래 연결된 게 자식
형제: 같은 부모 아래의 자식들끼리
리프(leaf, 리프·잎): 맨 끝, 자식이 없는 노드
레벨, 높이: 루트가 레벨 0, 그 아래가 1, …

트리: 루트 → 부모/자식 → 리프. 스토리 분기에 대응.

이진 트리

각 노드의 자식이 최대 2개만 있는 트리예요. 왼쪽 자식, 오른쪽 자식으로 구분합니다. 완전 이진 트리, 포화 이진 트리 같은 말이 시험에 나와요.

📖 어원 Tree(트리) = 나무, Root(루트) = 뿌리. 위에서 가지가 뻗어 내려가는 모양이 나무 같아서 그래요. 더 보기 →

문제 및 해설

트리에서 "맨 위 시작점", "자식이 없는 맨 끝 노드"를 각각 뭐라고 부르나요?

맨 위: 루트(root), 맨 끝 노드: 리프(leaf).

문제 및 답 확인

이진 트리는 한 노드의 자식이 최대 몇 개인가요?

답 보기

최대 2개. 왼쪽 자식, 오른쪽 자식으로 구분해요.

도전과제

풀어 본 뒤 정답을 펼쳐 확인하세요.

도전 1. 스토리 분기에서 "시작 → 선택 A → 엔딩1", "시작 → 선택 B → 엔딩2"처럼 갈라질 때, 트리로 보면 노드 개수는? (시작, A, B, 엔딩1, 엔딩2)

정답 보기

정답: 5개

루트=시작, 자식=A와 B. A의 자식=엔딩1, B의 자식=엔딩2. 노드는 시작, A, B, 엔딩1, 엔딩2로 5개. 리프는 엔딩1, 엔딩2 두 개예요.

도전 2. "완전 이진 트리"에서 리프 노드를 제외한 모든 노드가 자식을 2개 가지면, 높이 2인 완전 이진 트리의 노드 개수는? (루트=1, 레벨1=2, 레벨2=최대 4)

정답 보기

정답: 7개 (포화 이진 트리일 때)

레벨 0: 1개, 레벨 1: 2개, 레벨 2: 4개 → 1+2+4=7. 완전 이진 트리는 마지막 레벨만 왼쪽부터 채워지므로 4~7개일 수 있어요. "높이 2인 포화"면 7개.

문제 및 실습

트리 구조를 보고 루트·자식·리프를 눈으로 따라 가 보세요. 아래에서 파이썬 예제를 골라 바로 실행해 볼 수 있어요.

실습: 트리 →

📌 예제별 쓰는 API (리스트·스택·큐·정렬·이진탐색)

예제 버튼을 누르면 해당 뼈대 코드가 불러와져요. 예제별 사용 함수 요약이에요.

리스트: append(값), pop(인덱스)
스택: append(값), pop() (인자 없음)
큐: deque, append, popleft()
버블 정렬: 인덱싱 arr[j], 비교 >, 스왑 a,b = b,a
이진 탐색: (left+right)//2, left = mid+1 / right = mid-1

🐍 파이썬으로 실습 (이 페이지 안에서)

아래 코드창에 직접 코드를 써 보거나, 리스트·스택·큐·정렬·이진탐색 예제를 참고해 보세요.