핵심 정리
| 순회 | 방문 순서 | 자주 쓰는 곳 |
|---|---|---|
| 전위 | root, left, right | 구조 복사, 직렬화 |
| 중위 | left, root, right | BST를 오름차순으로 읽기 |
| 후위 | left, right, root | 하위 결과 합치기, 삭제 |
| 레벨 | 가까운 깊이부터 | 최단 깊이, 층별 처리 |
csharp
class Node
{
public int Value;
public Node? Left;
public Node? Right;
}구조
이진 트리는 각 노드가 최대 두 개의 자식을 갖는 트리입니다. 맨 위 노드는 root, 자식이 없는 노드는 leaf라고 부릅니다.
text
1
/ \
2 3
/ \
4 5트리 문제는 보통 “현재 노드에서 무엇을 하고, 왼쪽과 오른쪽 결과를 어떻게 합칠 것인가”로 읽습니다. 그래서 재귀와 잘 맞습니다.
csharp
int Count(Node? node)
{
if (node == null) return 0;
return 1 + Count(node.Left) + Count(node.Right);
}깊이 우선 순회
전위, 중위, 후위 순회는 모두 DFS입니다. 차이는 현재 노드를 언제 처리하느냐입니다.
csharp
void InOrder(Node? node)
{
if (node == null) return;
InOrder(node.Left);
Console.WriteLine(node.Value);
InOrder(node.Right);
}순회 선택
| 목표 | 순회 |
|---|---|
| 루트부터 구조 확인 | 전위 |
| BST 값을 정렬 순서로 얻기 | 중위 |
| 자식 계산 후 부모 계산 | 후위 |
| 깊이별로 처리 | 레벨 순회 |
| 최소 깊이 찾기 | BFS 레벨 순회 |
레벨 순회는 큐를 사용합니다.
csharp
var q = new Queue<Node>();
q.Enqueue(root);
while (q.Count > 0)
{
Node node = q.Dequeue();
if (node.Left != null) q.Enqueue(node.Left);
if (node.Right != null) q.Enqueue(node.Right);
}주의할 점
트리가 균형 잡혀 있지 않으면 높이가 n이 될 수 있습니다. 재귀 순회가 단순해 보여도 입력이 한쪽으로 긴 트리라면 스택 오버플로 위험이 있습니다.
또 중위 순회가 정렬 결과를 주는 것은 이진 트리 전체가 아니라 BST 조건을 만족할 때입니다.
참고 링크
1 sources