3. 트리 순회 | III단원

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

전위·중위·후위 순회 = 스토리 트리를 "어떤 순서로 장면을 방문할지" 정하는 것과 같아요. 전위는 현재 장면을 먼저 처리하고 자식(다음 선택지)으로, 후위는 자식들을 다 처리한 뒤 현재 장면(예: 결과 합산)을 할 때 씁니다. 중위는 이진 탐색 트리에서 정렬된 순서로 값을 꺼낼 때 쓰여요.

순회(Traversal, 트래버설)

트리의 모든 노드를 어떤 순서로 방문할지 정한 거예요. "나"를 언제 방문하느냐에 따라 이름이 달라져요.

전위 순회 (Preorder, 프리오더)

(나) → 왼쪽 → 오른쪽. 루트를 먼저 방문하고, 왼쪽 서브트리, 그다음 오른쪽 서브트리.

중위 순회 (Inorder, 인오더)

왼쪽 → (나) → 오른쪽. 왼쪽 다 보고, 나를 보고, 오른쪽을 봐요. 이진 탐색 트리에서는 중위 순회하면 정렬된 순서로 나와요.

후위 순회 (Postorder, 포스트오더)

왼쪽 → 오른쪽 → (나). 왼쪽, 오른쪽 다 방문한 뒤에 나를 방문해요.

문제 및 해설

📋 기출 유형

루트 1, 왼쪽 2(자식 4,5), 오른쪽 3(자식 6,7)인 이진 트리에서 중위 순회 결과는?

정답: 4, 2, 5, 1, 6, 3, 7. 왼쪽→나→오른쪽이니까 1 기준 왼쪽(2 전체) → 1 → 오른쪽(3 전체). 더 많은 예제 →

문제 및 답 확인

같은 트리에서 전위 순회(나→왼쪽→오른쪽) 결과는?

답 보기

1, 2, 4, 5, 3, 6, 7. 루트 1 먼저, 그다음 왼쪽 서브트리(2,4,5), 그다음 오른쪽(3,6,7).

도전과제

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

도전 1. 루트 1, 왼쪽 자식 2(리프), 오른쪽 자식 3(리프)인 트리에서 후위 순회(왼쪽→오른쪽→나) 결과는?

정답 보기

정답: 2, 3, 1

왼쪽(2) → 오른쪽(3) → 나(1) 순서. 후위는 "자식들을 다 방문한 뒤에 루트"라서, 스토리에서는 "모든 선택을 본 뒤에 시작 장면 정리"할 때 쓸 수 있어요.

도전 2. 게임에서 "장면 트리"를 전위 순회하면 어떤 순서로 장면을 방문하게 되나요? (한 줄로)

정답 보기

정답: 나(현재 장면) 먼저 처리한 뒤, 왼쪽 서브트리(첫 번째 선택지 이하) 전체, 그다음 오른쪽 서브트리(두 번째 선택지 이하) 전체.

즉 "지금 장면 연출 → 첫 번째 선택 분기 쭉 탐색 → 두 번째 선택 분기 쭉 탐색" 순서예요.

문제 및 실습

전위·중위·후위 순회를 버튼으로 한 단계씩 따라 가 보세요. 아래에서 파이썬 예제를 골라 바로 실행해 볼 수 있어요.

실습: 트리 순회 →

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

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

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

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

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