트리 구조 개요
트리는 계층적 관계를 표현하는 비선형 자료구조로, 유한 개의 노드로 구성된다. 루트 노드에서 시작하여 각 노드는 자식 노드들을 가질 수 있으며, 전체 구조는 순환하지 않는다.
기본 용어
- 노드의 차수(Degree): 자식 노드의 수. 예를 들어 A 노드가 3개의 자식을 가지면 차수는 3.
- 단말 노드(Leaf Node): 자식이 없는 노드.
- 부모/자식 노드(Parent/Child): 상하위 관계에 있는 두 노드.
- 레벨(Level): 루트를 1레벨로 하여 아래로 내려갈수록 증가.
- 트리의 높이(Height): 가장 깊은 레벨의 값.
- 서브트리(Subtree): 특정 노드를 루트로 하는 하위 트리.
- 삼림(Forest): 서로 분리된 여러 개의 트리 집합.
이진 트리(Binary Tree)
각 노드가 최대 두 개의 자식 노드(왼쪽, 오른쪽)만을 가지는 트리 구조이다. 다음 두 가지 경우를 포함한다:
- 빈 트리 (노드 없음)
- 루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리
특수 형태의 이진 트리
- 포화 이진 트리(Full Binary Tree): 모든 레벨에서 노드가 가득 찬 상태.
- 완전 이진 트리(Complete Binary Tree): 마지막 레벨을 제외하고 모든 레벨이 채워져 있으며, 마지막 레벨은 왼쪽부터 연속적으로 채워져 있음.
주요 성질
- 레벨 \( h \) 에 있는 노드 수는 최대 \( 2^{h-1} \).
- 깊이 \( h \) 인 트리의 최대 노드 수는 \( 2^h - 1 \).
- 단말 노드 수 \( N_0 \), 차수가 2인 노드 수 \( N_2 \) 일 때, \( N_0 = N_2 + 1 \).
- 노드 수 \( N \) 인 포화 이진 트리의 높이는 \( \log_2(N+1) \).
- 배열 기반 저장 시, 인덱스 \( i \) 인 노드의 부모는 \( \lfloor(i-1)/2\rfloor \), 자식은 \( 2i+1 \) 및 \( 2i+2 \).
이진 트리의 순회 방식
노드 정의
typedef char TreeNodeData;
typedef struct TreeNode {
TreeNodeData val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
TreeNode* createNode(TreeNodeData x) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
if (!node) exit(EXIT_FAILURE);
node->val = x;
node->left = node->right = NULL;
return node;
}
전위 순회 (Pre-order)
루트 → 왼쪽 → 오른쪽 순으로 방문.
void preorder(TreeNode* root) {
if (!root) {
printf("null ");
return;
}
printf("%c ", root->val);
preorder(root->left);
preorder(root->right);
}
중위 순회 (In-order)
왼쪽 → 루트 → 오른쪽.
void inorder(TreeNode* root) {
if (!root) {
printf("null ");
return;
}
inorder(root->left);
printf("%c ", root->val);
inorder(root->right);
}
후위 순회 (Post-order)
왼쪽 → 오른쪽 → 루트.
void postorder(TreeNode* root) {
if (!root) {
printf("null ");
return;
}
postorder(root->left);
postorder(root->right);
printf("%c ", root->val);
}
레벨 순서 순회 (Level-order)
큐를 이용해 레벨 단위로 탐색.
void levelOrder(TreeNode* root) {
if (!root) return;
Queue* q = createQueue();
enqueue(q, root);
while (!isEmpty(q)) {
int size = getSize(q);
for (int i = 0; i < size; ++i) {
TreeNode* curr = dequeue(q);
printf("%c ", curr->val);
if (curr->left) enqueue(q, curr->left);
if (curr->right) enqueue(q, curr->right);
}
printf("\n"); // 한 레벨 출력 후 줄바꿈
}
destroyQueue(q);
}
핵심 연산 함수들
노드 총 개수
int countNodes(TreeNode* root) {
if (!root) return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
리프 노드 수 계산
int countLeaves(TreeNode* root) {
if (!root) return 0;
if (!root->left && !root->right) return 1;
return countLeaves(root->left) + countLeaves(root->right);
}
트리의 높이
int treeHeight(TreeNode* root) {
if (!root) return 0;
int leftH = treeHeight(root->left);
int rightH = treeHeight(root->right);
return (leftH > rightH ? leftH : rightH) + 1;
}
k번째 레벨의 노드 수
int nodesAtLevelK(TreeNode* root, int k) {
if (!root || k < 1) return 0;
if (k == 1) return 1;
return nodesAtLevelK(root->left, k - 1) + nodesAtLevelK(root->right, k - 1);
}
특정 값 검색
TreeNode* findValue(TreeNode* root, TreeNodeData target) {
if (!root) return NULL;
if (root->val == target) return root;
TreeNode* found = findValue(root->left, target);
if (found) return found;
return findValue(root->right, target);
}
완전 이진 트리 여부 판단
bool isCompleteTree(TreeNode* root) {
if (!root) return true;
Queue* q = createQueue();
enqueue(q, root);
bool encounteredNull = false;
while (!isEmpty(q)) {
TreeNode* curr = dequeue(q);
if (!curr) {
encounteredNull = true;
} else {
if (encounteredNull) {
destroyQueue(q);
return false;
}
enqueue(q, curr->left);
enqueue(q, curr->right);
}
}
destroyQueue(q);
return true;
}
힙(Heap) 구조
힙은 완전 이진 트리를 배열로 표현한 자료구조로, 다음 두 종류가 있다:
- 최소 힙(Min-Heap): 부모 노드 ≤ 자식 노드
- 최대 힙(Max-Heap): 부모 노드 ≥ 자식 노드
상향 조정 (삽입 시 사용)
void heapifyUp(int arr[], int child) {
while (child > 0) {
int parent = (child - 1) / 2;
if (arr[child] < arr[parent]) {
swap(&arr[child], &arr[parent]);
child = parent;
} else break;
}
}
하향 조정 (삭제 시 사용)
void heapifyDown(int arr[], int size, int parent) {
int child = parent * 2 + 1;
while (child < size) {
// 오른쪽 자식이 존재하고 더 작으면 선택
if (child + 1 < size && arr[child + 1] < arr[child])
++child;
if (arr[parent] > arr[child]) {
swap(&arr[parent], &arr[child]);
parent = child;
child = parent * 2 + 1;
} else break;
}
}
힙 정렬 (Heap Sort)
void heapSort(int arr[], int n) {
// 하향 조정으로 초기 힙 생성 (O(n))
for (int i = (n - 2) / 2; i >= 0; --i)
heapifyDown(arr, n, i);
// 정렬 수행
for (int end = n - 1; end > 0; --end) {
swap(&arr[0], &arr[end]);
heapifyDown(arr, end, 0);
}
}
Top-K 문제 해결 (예: 상위 K개 원소 찾기)
void topKElements(FILE* file, int k) {
int* minHeap = (int*)malloc(k * sizeof(int));
int count = 0;
// 처음 K개 요소로 최소 힙 구성
while (count < k && fscanf(file, "%d", &minHeap[count]) != EOF) {
heapifyUp(minHeap, count);
++count;
}
// 나머지 원소 비교
int value;
while (fscanf(file, "%d", &value) != EOF) {
if (value > minHeap[0]) {
minHeap[0] = value;
heapifyDown(minHeap, k, 0);
}
}
// 결과 출력
for (int i = 0; i < k; ++i)
printf("%d ", minHeap[i]);
free(minHeap);
}
연습 문제 풀이 패턴
단일 값 트리 확인
bool isUnivalued(TreeNode* root) {
if (!root) return true;
if (root->left && root->left->val != root->val) return false;
if (root->right && root->right->val != root->val) return false;
return isUnivalued(root->left) && isUnivalued(root->right);
}
두 트리 동일성 비교
bool areIdentical(TreeNode* a, TreeNode* b) {
if (!a && !b) return true;
if (!a || !b) return false;
return (a->val == b->val) &&
areIdentical(a->left, b->left) &&
areIdentical(a->right, b->right);
}
대칭 트리 판별
bool isMirror(TreeNode* left, TreeNode* right) {
if (!left && !right) return true;
if (!left || !right) return false;
return (left->val == right->val) &&
isMirror(left->left, right->right) &&
isMirror(left->right, right->left);
}
bool isSymmetric(TreeNode* root) {
return !root || isMirror(root->left, root->right);
}