Quick Comparison
이진 트리는 각 노드가 최대 두 자식을 갖는 구조이고, 전위·중위·후위·레벨 순회는 노드를 방문하는 순서를 다르게 정합니다. 중위 순회가 정렬 결과가 되는 것은 BST 규칙을 만족할 때뿐입니다.
| 순회 | 방문 순서 | 자주 쓰는 곳 |
|---|---|---|
| 전위 | root, left, right | 구조 복사, 직렬화 |
| 중위 | left, root, right | BST를 오름차순으로 읽기 |
| 후위 | left, right, root | 하위 결과 합치기, 삭제 |
| 레벨 | 가까운 깊이부터 | 최단 깊이, 층별 처리 |
구조
이진 트리는 각 노드가 최대 두 개의 자식을 갖는 트리입니다. 맨 위 노드는 root, 자식이 없는 노드는 leaf라고 부릅니다.
일반 트리는 자식 수를 둘로 제한하지 않아 파일 시스템, UI hierarchy, scene graph처럼 children 목록으로 표현하는 경우가 많습니다. Tree에서는 root에서 한 node까지 경로가 하나지만 일반 graph는 cycle과 여러 경로를 가질 수 있어 방문 집합이 필요합니다.
1
/ \
2 3
/ \
4 5트리 문제는 보통 “현재 노드에서 무엇을 하고, 왼쪽과 오른쪽 결과를 어떻게 합칠 것인가”로 읽습니다. 그래서 재귀와 잘 맞습니다. 이진 트리는 BST와 다릅니다. BST는 왼쪽 값이 작고 오른쪽 값이 큰 정렬 규칙을 추가한 트리이고, 힙은 부모와 자식 사이의 우선순위만 보장합니다.
sealed class Node
{
public int Value { get; }
public Node? Left { get; init; }
public Node? Right { get; init; }
public Node(int value) => Value = value;
}
static int Count(Node? node)
{
if (node == null) return 0;
return 1 + Count(node.Left) + Count(node.Right);
}깊이 우선 순회
전위, 중위, 후위 순회는 모두 DFS입니다. 차이는 현재 노드를 언제 처리하느냐입니다. 노드 수가 N, 트리 높이가 H이면 세 DFS 순회는 시간 O(N), 재귀 호출을 위한 공간 O(H)입니다. 편향 트리는 H = N이 될 수 있습니다.
void InOrder(Node? node)
{
if (node == null) return;
InOrder(node.Left);
Console.WriteLine(node.Value);
InOrder(node.Right);
}순회 선택
| 목표 | 순회 |
|---|---|
| 루트부터 구조 확인 | 전위 |
| BST 값을 정렬 순서로 얻기 | 중위 |
| 자식 계산 후 부모 계산 | 후위 |
| 깊이별로 처리 | 레벨 순회 |
| 최소 깊이 찾기 | BFS 레벨 순회 |
레벨 순회는 큐를 사용하며 시간 O(N), 가장 넓은 층의 노드 수만큼 O(N) 보조 공간을 쓸 수 있습니다. 빈 루트를 큐에 넣으면 이후 null 접근 문제가 생기므로 먼저 처리합니다.
static List<int> LevelOrder(Node? root)
{
if (root == null) return [];
var order = new List<int>();
var queue = new Queue<Node>();
queue.Enqueue(root);
while (queue.TryDequeue(out Node node))
{
order.Add(node.Value);
if (node.Left != null) queue.Enqueue(node.Left);
if (node.Right != null) queue.Enqueue(node.Right);
}
return order;
}주의할 점
트리가 균형 잡혀 있지 않으면 높이가 n이 될 수 있습니다. 재귀 순회가 단순해 보여도 입력이 한쪽으로 긴 트리라면 스택 오버플로 위험이 있습니다.
또 중위 순회가 정렬 결과를 주는 것은 이진 트리 전체가 아니라 BST 조건을 만족할 때입니다.
참고 링크
2 sources