한양과기고 에듀테크 수업도구 대시보드

계층으로 이어진 노드들, 그리고 그걸 훑는 네 가지 방법

트리(Tree)는 배열이나 리스트처럼 한 줄로 늘어서지 않고, 한 노드가 여러 자식을 거느리는 계층 구조다. 그중에서도 이진 트리(Binary Tree)는 각 노드가 자식을 최대 2개(왼쪽·오른쪽)만 가질 수 있는 가장 단순한 형태다. 값의 크기 규칙은 아직 없다 — 그냥 "누가 누구의 자식인가"만 정해진 순수한 모양이다. 이 페이지에서는 트리의 기본 용어와 모양, 그리고 트리 전체를 빠짐없이 훑는 4가지 순회(Traversal) 방법을 직접 눌러 보며 익힌다.

1 트리 용어 정리 — 클릭해서 확인해 보자

왼쪽 트리는 이 페이지의 예시다. 오른쪽 버튼을 눌러 각 용어가 트리의 어느 부분을 가리키는지 확인하자.

2 이진 트리의 다섯 가지 모양

Full (정 트리)

모든 노드의 자식이 0개 또는 2개. 1개짜리 자식은 없다.

Complete (완전)

마지막 레벨을 제외하곤 꽉 차 있고, 마지막 레벨은 왼쪽부터 채운다.

Perfect (포화)

모든 레벨이 완전히 꽉 참. 리프의 깊이가 전부 같다.

Balanced (균형)

모든 노드에서 좌우 서브트리 높이 차가 1 이하. 모양이 예쁘진 않아도 된다.

Degenerate (편향)

모든 노드가 자식을 하나만 가짐. 사실상 연결 리스트와 같다.

3 직접 만들고 네 가지로 순회해 보기

노드 수: 0 트리 높이: 0

순회 버튼을 누르면 방문 순서가 여기 표시된다.

큐 상태는 여기 표시된다 (레벨 순회 전용) — 앞의 세 순회와 달리 재귀 대신 큐를 쓴다.

예시 트리가 준비되어 있다. 순회 버튼을 눌러 보자.

4 순회별로 실제로 어디에 쓰나

순회	방문 순서	대표 활용
전위 (Preorder)	나 → 왼 → 오	트리 복사·직렬화. 나 자신을 먼저 기록해 두면, 나중에 그 순서 그대로 다시 읽으면서 루트부터 순서대로 트리를 재구성할 수 있다.
중위 (Inorder)	왼 → 나 → 오	이진 탐색 트리(BST)에서 값을 정렬된 순서 그대로 뽑아낼 때 쓴다. "왼쪽은 작고 오른쪽은 크다"는 규칙과 만나면 중위 순회가 곧 오름차순 정렬이 된다.
후위 (Postorder)	왼 → 오 → 나	자식부터 안전하게 처리해야 하는 작업. 폴더 크기를 하위 폴더부터 더해 올라가며 계산하거나, 트리(디렉터리)를 삭제할 때 자식을 먼저 지워야 부모를 지울 수 있다.
레벨 순회 (Level-order)	큐로 한 층씩	너비 우선 탐색(BFS) 계열의 기본형. 그래프 탐색(BFS/DFS)이나 "가장 가까운 것부터" 찾는 최단 경로 문제의 출발점이다.

5 다음 단계

지금까지 만든 트리는 값이 어디에 들어가는지에 대한 규칙이 없다 — 그냥 "다음 빈 자리"에 순서대로 채웠을 뿐이다. 여기에 딱 한 가지 규칙만 추가하면 완전히 다른 자료구조가 된다: "왼쪽 서브트리는 나보다 작고, 오른쪽 서브트리는 나보다 크다." 이 규칙 하나가 생기는 순간, 방금 배운 중위 순회는 트리를 정렬된 순서로 읽어내는 도구가 되고, 검색은 매번 절반씩 후보를 버리는 빠른 연산이 된다. 바로 이진 탐색 트리(BST)다.

6 네 가지 순회, 코드로 보면

# 전위 순회 (Preorder) — 나 → 왼쪽 → 오른쪽 def preorder(node): if node is None: return visit(node) # 나를 먼저 처리 preorder(node.left) preorder(node.right) # 중위 순회 (Inorder) — 왼쪽 → 나 → 오른쪽 def inorder(node): if node is None: return inorder(node.left) visit(node) # 왼쪽을 다 끝낸 뒤 나 inorder(node.right) # 후위 순회 (Postorder) — 왼쪽 → 오른쪽 → 나 def postorder(node): if node is None: return postorder(node.left) postorder(node.right) visit(node) # 자식을 모두 처리한 뒤 마지막에 나 # 레벨 순회 (Level-order) — 재귀(DFS) 대신 큐(Queue)를 쓰는 BFS from collections import deque def level_order(root): if root is None: return queue = deque([root]) # 큐에 루트만 넣고 시작 while queue: node = queue.popleft() # 맨 앞에서 꺼낸다 (FIFO) visit(node) if node.left: queue.append(node.left) if node.right: queue.append(node.right)

앞의 세 순회는 전부 재귀 호출로 자기 자신(스택)을 타고 내려갔다 올라온다 — 그래서 "깊이 우선(DFS)"이다. 레벨 순회만 큐(Queue)에 다음에 봐야 할 노드를 쌓아두고 앞에서부터 꺼내 쓴다 — 그래서 "너비 우선(BFS)"이고, 결과가 한 층씩 나온다.

📌 한 줄 정리 — 트리는 계층 구조이고, 순회는 그 계층을 빠짐없이 훑는 순서다. 전위·중위·후위는 재귀(DFS)로 "나 자신을 언제 처리하느냐"만 다를 뿐이고, 레벨 순회만 큐(BFS)로 층별로 훑는다. 다음엔 여기에 크기 규칙 하나를 더한 이진 탐색 트리를 만나 보자.