20260521 데이터구조와알고리즘 12주차
트리(Tree) 강의 핵심 요약
이번 강의 핵심은:
트리는 "계층 구조"를 표현하는 자료구조다
이거였음.
리스트, 스택, 큐는 선형 구조인데,
트리는 부모-자식 관계로 연결된 계층 구조를 표현함.
대표 예시:
- 폴더 구조
- 조직도
- 게임 스킬트리
- 결정 트리
- AI 의사결정
1. 트리 기본 개념
트리는:
노드(node) + 간선(edge)
으로 구성됨.
핵심 용어
루트 노드(root)
부모가 없는 최상위 노드
부모 / 자식 노드
연결 관계 그대로.
형제 노드
같은 부모를 가진 노드
단말 노드(leaf)
자식이 없는 노드
비단말 노드
자식이 하나 이상 있는 노드
서브트리(subtree)
특정 노드를 기준으로 아래 전체 구조
레벨(level)
트리 층수
높이(height)
최대 레벨
차수(degree)
자식 개수
2. 이진 트리(Binary Tree)
강의 핵심:
모든 노드가 최대 2개의 자식을 가지는 트리
즉:
- left
- right
두 방향만 존재.
3. 교수님이 엄청 강조한 함정
이거 시험 함정이라고 계속 말함 ㅋㅋ
공집합도 이진트리인가?
정답:
YES
노드 하나도 없어도:
공집합 이진트리
로 인정함.
많이 틀린다고 강조함.
4. 이진트리 특징
노드 n개
간선:
n - 1개
노드 최대 자식 수
2개 이하
서브트리 순서 존재
왼쪽/오른쪽 구분됨.
이게 일반 트리랑 큰 차이.
5. 포화 이진트리 (Full Binary Tree)
핵심:
모든 레벨이 꽉 차 있는 트리
특징
예를 들어 높이 4면:
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
이런 느낌으로 빈칸 없음.
노드 개수
높이가 k면:
2^k - 1
교수님이:
공식 암기보다 직접 유도할 줄 알아야 한다
라고 강조함.
6. 완전 이진트리 (Complete Binary Tree)
시험 단골 함정.
정의
마지막 레벨 전까지는 모두 꽉 차 있고
마지막 레벨은 왼쪽부터 순서대로 채워짐
중요 특징
이거 매우 중요:
중간에 구멍이 있으면 안됨
예:
1 2 3 4 5 _ 7
이런 식이면 완전 이진트리 아님.
교수님이:
5 다음에 6 없이 7 나오면 틀린 구조
라고 강조함.
7. 배열을 이용한 트리 표현
강의 핵심:
노드 번호를 배열 인덱스로 사용
부모/자식 공식
노드 i 기준:
부모:
\left\lfloor \frac{i}{2} \right\rfloor
왼쪽 자식:
2i
오른쪽 자식:
2i+1
8. 배열 표현의 단점
교수님이 바로 짚은 부분.
경사 트리(skewed tree) 같은 경우:
중간 배열칸이 비어버림
즉:
메모리 낭비 심함
9. 링크 표현법 (포인터 기반)
실무에서 더 많이 씀.
구조체 형태
typedef struct TreeNode {
int data;
struct TreeNode *left, *right;
} TreeNode;
10. 링크 표현 핵심
각 노드가:
- 데이터 저장
- 왼쪽 자식 주소 저장
- 오른쪽 자식 주소 저장
함.
즉:
포인터로 노드끼리 연결
하는 구조.
11. 동적 메모리 할당
n1 = (TreeNode *)malloc(sizeof(TreeNode));
이런 식으로 노드 생성.
연결 방식
n1->left = n2;
n1->right = n3;
즉:
부모가 자식 노드 주소를 가리킴
12. 트리 순회(Traversal)
이번 강의 핵심 중 핵심.
교수님이:
트리는 결국 어떻게 "순회"하느냐가 핵심
느낌으로 설명함.
13. 순회란?
트리 노드를 규칙적으로 방문하는 것
14. 3가지 순회 방식
전위 순회 (Preorder)
순서:
VLR
즉:
루트 → 왼쪽 → 오른쪽
중위 순회 (Inorder)
순서:
LVR
즉:
왼쪽 → 루트 → 오른쪽
후위 순회 (Postorder)
순서:
LRV
즉:
왼쪽 → 오른쪽 → 루트
15. 교수님이 강조한 핵심
V(루트)를 언제 방문하느냐가 핵심
16. 전위 순회 특징
루트를 가장 먼저 방문
순서:
루트
→ 왼쪽 서브트리 전체
→ 오른쪽 서브트리 전체
활용
- 문서 구조 출력
- 디렉토리 구조 표현
17. 중위 순회 특징
왼쪽 → 루트 → 오른쪽
특징
이진 탐색 트리에서는:
오름차순 정렬 결과
나옴.
활용
수식 트리 출력
18. 후위 순회 특징
자식 먼저 처리 후 부모 처리
활용
- 디렉토리 용량 계산
- 수식 계산
왜냐면:
하위 계산 끝내야 상위 계산 가능
하기 때문.
19. 순환 호출(재귀)
강의 전체 흐름:
트리 = 재귀 구조
였음.
이유
트리 안에:
또 다른 트리(서브트리)
가 계속 들어있기 때문.
교수님이:
이진트리 안에 또 이진트리
라고 계속 설명함.
20. 반복적 순회
재귀 말고:
스택 직접 사용
해서 구현 가능.
핵심
재귀 호출 내부적으로:
스택 사용
하기 때문.
21. 레벨 순회(Level Order)
이건 완전 다른 방식.
특징
층별로 방문
함.
예:
1층 → 2층 → 3층
순서.
22. 레벨 순회의 핵심
여기 중요:
큐(queue) 사용
이유
먼저 들어온 노드를 먼저 처리해야:
레벨 순서 유지
가능하기 때문.
23. 수식 트리(Expression Tree)
강의 후반 핵심.
구조
비단말 노드:
연산자
단말 노드:
피연산자
24. 수식 계산 방식
핵심:
후위 순회 사용
이유
자식 계산 끝내야:
부모 연산 가능
하기 때문.
25. evaluate 함수 핵심
op1 = evaluate(left);
op2 = evaluate(right);
이후:
switch(root->data)
로 계산.
즉:
재귀적으로 아래부터 계산
함.
26. 디렉토리 용량 계산
이것도 후위 순회 사용.
이유
하위 폴더 용량 다 더한 뒤:
현재 폴더 용량 계산
해야 하기 때문.
교수님 전체 메시지 요약
이번 강의 핵심은 단순히:
트리를 외워라
가 아니었음.
진짜 핵심은:
트리는 "재귀적 계층 구조"이고
순회 방식에 따라 완전히 다르게 동작한다
이거였음.
그리고:
VLR / LVR / LRV
이거 진짜 시험에 잘 나오는 부분이라
루트(V)를 언제 방문하는지 기준으로 이해해야 안 헷갈림.