14 — 트리 순회 개념

람다가 같은 트리 그림을 손가락으로 짚으며 "이 트리를 어떤 순서로 읽어야 해?"라고 묻고, 제네릭이 "나는 맨 위부터 읽었는데, 너는 왼쪽 끝부터 읽었네?"라며 서로 다른 순서로 읽은 걸 발견하자, 돌핀쌤이 "루트를 언제 읽느냐에 따라 순서가 달라져요. 그게 바로 순회예요"라고 안내하는 도입

🙋‍♀️ 람다: "선생님, 같은 트리인데 제네릭이는 1, 2, 4, 5, 3 으로 읽고 저는 4, 2, 5, 1, 3 으로 읽었어요. 둘 다 모든 노드를 한 번씩 들렀는데 순서가 다르네요?"

🐬 돌핀쌤: "둘 다 맞아요! 트리는 가지가 여러 방향으로 뻗어 있어서, 루트를 언제 읽느냐에 따라 순서가 달라져요. 트리의 모든 노드를 정해진 순서로 방문하는 걸 순회(Traversal) 라고 해요. 오늘은 그중 중위 순회 하나를 제대로 익혀볼게요. 지난 시간에 배운 재귀도 다시 만날 거예요."

🎯 오늘 완성할 코드는?

오늘 우리가 만들 건 중위 순회(inorder) 예요. 트리의 노드를 왼쪽 → 루트 → 오른쪽 순서로 하나씩 방문하며 출력하는 코드랍니다.

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

# 중위 순회(inorder) — 왼쪽 → 루트 → 오른쪽
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

root = Node(5)
root.left = Node(3)
root.right = Node(8)

def inorder(node):
    if node is None:            # 기저 조건: 빈 자리면 멈춤
        return
    inorder(node.left)          # ① 왼쪽 서브트리 먼저
    print(node.value)           # ② 현재 노드(루트) 출력
    inorder(node.right)         # ③ 오른쪽 서브트리 나중

inorder(root)    # 중위: 3 5 8

실행하면 이렇게 나와요.

3
5
8

이 트리는 이렇게 생겼어요. 왼쪽(3) → 루트(5) → 오른쪽(8) 순서로 읽힌 게 보이죠?

       [5]
      /   \
   [3]   [8]

🐬 돌핀쌤: "트리를 만드는 Node 부분까지 합쳐도 짧죠? 진짜 핵심은 inorder 함수 세 줄이에요. 지금부터 이 코드가 왜 왼쪽부터 차례로 읽어내는지 하나씩 풀어볼게요."

💡 어떻게 풀까? — 루트를 '가운데'에 읽기

트리는 리스트처럼 한 줄로 늘어서 있지 않아요. 가지가 양쪽으로 갈라져서, 어느 쪽을 먼저 읽을지를 우리가 정해 줘야 해요.

중위 순회의 규칙은 딱 하나예요. "왼쪽을 다 읽고 → 나(루트)를 읽고 → 오른쪽을 읽는다"

       [5]   ← ② 가운데에 읽음
      /   \
   [3]   [8]
    ↑       ↑
 ① 왼쪽 먼저  ③ 오른쪽 나중

그래서 이름이 중위(In-order) 예요. 루트를 가운데(In) 에서 읽는다는 뜻이지요. 결과는 3 → 5 → 8, 루트(5)가 한가운데에 왔어요.

🙋‍♀️ 람다: "제가 왼쪽 끝부터 읽어서 루트가 중간에 왔던 게, 바로 이 중위 순회였던 거네요!"

이 규칙은 큰 트리에서도 똑같아요. 왼쪽 가지 안에 또 작은 트리가 있으면, 그 작은 트리도 "왼쪽 → 루트 → 오른쪽"으로 읽으면 돼요. 같은 규칙을 자식에게 그대로 시키는 것 — 이게 바로 재귀랍니다.

🔍 코드 한 줄씩 뜯어보기

이제 맨 위에서 본 완성 코드를 한 줄씩 볼게요.

① 노드 한 칸을 만들어요

class Node:
    def __init__(self, value):
        self.value = value     # 이 노드가 가진 값
        self.left = None       # 왼쪽 자식 (없으면 None)
        self.right = None      # 오른쪽 자식 (없으면 None)

트리는 노드들이 연결된 모양이에요. 노드 하나는 자기 값과, 왼쪽·오른쪽 자식으로 가는 길을 가져요. 아직 자식이 없으면 None(빈 자리)으로 둬요. (13차시에서 만든 그 Node 예요.)

② 트리를 조립해요

root = Node(5)
root.left = Node(3)
root.right = Node(8)

루트(5)를 만들고, 그 왼쪽에 3, 오른쪽에 8을 연결했어요. 이러면 맨 위에서 본 그 트리가 완성돼요.

③ 빈 자리면 멈춰요 (기저 조건)

    if node is None:            # 기저 조건: 빈 자리면 멈춤
        return

순회 함수의 첫 줄은 항상 "지금 자리가 비었는지" 확인이에요. 비어 있으면(None) 더 갈 곳이 없으니 그냥 돌아와요. 이 줄을 빠뜨리면 빈 자리에서 None.left 를 읽으려다 오류가 나요.

④ 왼쪽 → 나 → 오른쪽 순서로 읽어요

    inorder(node.left)          # ① 왼쪽 서브트리 먼저
    print(node.value)           # ② 현재 노드(루트) 출력
    inorder(node.right)         # ③ 오른쪽 서브트리 나중

여기가 심장이에요. 왼쪽 자식에게 똑같은 inorder 를 먼저 시키고, 그게 다 끝나면 내 값을 출력하고, 마지막으로 오른쪽 자식에게 inorder 를 시켜요.

💡 핵심은 print 의 위치예요. print 를 왼쪽 호출과 오른쪽 호출 사이(가운데) 에 둔 게 바로 중위 순회예요. 이 한 줄을 맨 앞이나 맨 뒤로 옮기면 순서가 완전히 달라져요(→ 더 해보기에서!).

⑤ 전체가 어떻게 굴러가는지 — 트리 [5, 3, 8]

inorder(root) 를 부르면 이렇게 흘러가요.

inorder(5) 시작
 ├─ inorder(3) 먼저   → 3의 왼쪽(None) 멈춤 → print(3) → 3의 오른쪽(None) 멈춤
 ├─ print(5)          ← 왼쪽을 다 읽은 뒤 루트 5 출력
 └─ inorder(8)        → 8의 왼쪽(None) 멈춤 → print(8) → 8의 오른쪽(None) 멈춤

출력 순서: 3 → 5 → 8

🙋‍♂️ 제네릭: "왼쪽 3을 완전히 끝낸 다음에 5를 찍고, 그다음에 8로 가네요. print 가 가운데 있어서 루트가 딱 중간에 나왔어요!"

✍️ 직접 완성해보기

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

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

root = Node(5)
root.left = Node(3)
root.right = Node(8)

def inorder(node):
    if node is ___:             # 기저 조건: 빈 자리면 멈춤
        return
    inorder(node.___)           # ① 왼쪽 서브트리 먼저 (left)
    print(node.value)           # ② 현재 노드(루트) 출력
    inorder(node.___)           # ③ 오른쪽 서브트리 나중 (right)

inorder(root)    # 중위: 3 5 8

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

📌 오늘 배운 것

개념	설명
순회(Traversal)	트리의 모든 노드를 정해진 순서로 한 번씩 방문하는 것
중위 순회(inorder)	왼쪽 → 루트 → 오른쪽 순서로 방문
기저 조건	`if node is None: return` — 빈 자리면 멈춤(빠뜨리면 오류)
재귀	자식 서브트리에게 같은 함수를 그대로 시킴
`print` 위치	왼쪽·오른쪽 호출 사이(가운데) 에 두면 중위 순회

🐬 돌핀쌤: "빈 자리면 멈추고, 왼쪽 → 나 → 오른쪽! 이 세 박자가 중위 순회의 전부예요. 잘했어요! 👏"

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

여기까지가 오늘의 필수 내용이에요. 아래는 여유 있을 때 도전하는 내용이고, 예제 문제로 직접 풀어볼 수 있어요. 외울 필요는 없어요. 놀랍게도 전부 오늘 만든 inorder 와 함수 모양이 똑같고, print(node.value) 한 줄의 위치만 바뀐답니다.

전위 순회(preorder) — print 를 맨 앞으로 옮기면 돼요. 루트 → 왼쪽 → 오른쪽 순서가 되고, 같은 트리에서 5 3 8 이 나와요. 트리 복사나 폴더 구조 출력에 써요. → 예제로 연습
후위 순회(postorder) — print 를 맨 뒤로 옮기면 돼요. 왼쪽 → 오른쪽 → 루트 순서가 되고, 3 8 5 가 나와요. 폴더 삭제나 폴더 용량 계산(자식 먼저)에 써요. → 예제로 연습

print 위치만 바꾸면:
  맨 앞  → 전위(preorder): 루트 → 왼 → 오
  가운데 → 중위(inorder) : 왼 → 루트 → 오   ← 오늘 배운 것
  맨 뒤  → 후위(postorder): 왼 → 오 → 루트

BST를 중위 순회하면 정렬된다 — 이진 탐색 트리(BST)는 왼쪽 < 현재 < 오른쪽 규칙을 지켜요. 그래서 BST를 중위 순회하면 따로 정렬하지 않아도 작은 값부터 큰 값 순서로 나와요. → 예제로 연습

BST를 중위 순회하면 1~9가 오름차순으로 나오는 과정을 화살표로 표시

BST 예:
       [5]
      /   \
   [3]   [7]
   / \   / \
 [1] [4][6] [9]

중위 순회: 1 → 3 → 4 → 5 → 6 → 7 → 9   ← 정렬된 순서!

🐬 돌핀쌤: "기본(중위)을 완벽히 익힌 다음 도전하세요. 전위·후위도 결국 같은 뼈대에 print 한 줄을 위아래로 옮긴 것뿐이에요."

14 — 트리 순회 개념

📃 해결할 문제

💻 예제 입력 1

🖨️ 예제 출력 1