Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 수학
- 문자열
- BFS
- Baekjoon
- 문제풀이
- solvedac
- greedy
- 그래프탐색
- 정렬
- 코테
- DFS
- 백준
- dp
- 자료구조
- PYTHON
- 코딩테스트
- 그래프
- 반복문
- Datastructure
- 알고리즘
- 그리디
- 파이썬
- 다이나믹프로그래밍
- 데이터마이닝
- 너비우선탐색
- DP알고리즘
- 큐
- 깊이우선탐색
- 프로그래머스
- 그리디알고리즘
Archives
- Today
- Total
nyunu
[자료구조] 이진트리 정의 (in python) 본문
728x90
강의 출처) 숙명여자대학교 소프트웨어융합전공 강의 "자료구조", 이현자 교수님
1. 트리
: 계층적 자료의 표현에 적합한 자료 구조
= 루트 노드 + 서브 트리
2. 이진트리
1) 이진트리란 ?
: 모든 노드가 2개의 서브 트리(노드)를 갖는 트리
- 서브 트리는 공집합일 수도 있음
- 루트와 왼쪽 서브트리 & 오른쪽 서브트리로 구성된 노드들의 집합
- 이진트리의 서브트리는 모두 이진트리
2) 허프만 코드 트리
: 문자에 대한 컴퓨터 내부 표현 중 하나 -> 텍스트 문서 압축
- 빈도수가 높은 문자에 대해서는 짧은 코드를 부여
- 빈도수가 적은 문자에 대해서는 긴 코드를 부여
- 결론적으로 최대한 적은 비트만 차지하도록 하는 것
3) 트리 관련 용어
- 노드 : 데이터와 연결선으로 구성된 트리의 한 유닛
- 노드의 차수 : 해당 노드의 자식 노드 개수
- 트리의 차수 : 모든 노드의 차수 중 최대값
- 단말 노드 (leaf [terminal] node) : 자식 노드가 없는 트리의 가장 끝에 위치한 노드
- 비단말 노드 : 단말 노드를 제외한 모든 노드
- 깊이 (level) : 루트 노드(0) ~> 단말 노드 방향으로 1씩 증가
- 부모 노드 : 노드의 부모노드라면 노드보다 level이 1만큼 작은 노드를 의미
- 자식 노드 : 노드의 자식노드라면 노드보다 level이 1만큼 큰 노드를 의미
- 형제 노드 : 같은 부모 노드를 가지는 노드들
- 조상 노드 : 노드 ~ 루트 노드 사이의 노드들
- 후손 노드 : 노드의 자식노드 이후의 모든 노드들
- 노드의 깊이 : 루트노드 ~ 노드 연결선의 수
- 노드의 높이 : 노드 ~ 단말노드 연결선의 수
- 트리의 높이 = 트리의 깊이 (루트노드 ~ 단말노드)
4) 최대 노드의 수
(1) 각 레벨에서의 최대 노드 수

- 트리의 레벨
ex) 루트 노드의 level = 0 -> 1
(2) 트리 높이에 따른 최대 노드 수

- 포화 이진트리
-> -1의 의미 : 루트노드는 한 개니까 !
5) 트리 종류
(1) 포화 이진 트리
- 모든 노드가 2개의 자식 노드를 가지는 트리
- 모든 리프 노드의 레벨이 동일함
(2) 완전 이진 트리
- 포화 이진 트리의 leaf들이 오른쪽부터 제거되면서 얻어진 트리
- 높이가 h일 때, 레벨 1부터 h-1까지는 노드가 모두 채워져 있고
- 마지막 레벨 h에서는 왼쪽 -> 오른쪽 방향으로 노드가 채워져 있음
728x90
'Data Structure & Algorithm' 카테고리의 다른 글
[자료구조] 이진트리 응용 - 평가트리 (in python) (0) | 2023.06.18 |
---|---|
[자료구조] 이진트리 표현법 (in python) (1) | 2023.06.18 |
[자료구조] 원형 리스트, 이중 리스트 구현 (in python) (1) | 2023.06.18 |
[자료구조] 단일 연결 리스트 구현 (in python) (0) | 2023.06.18 |
[자료구조] 수식 평가_중위, 후위, 전위 (in python) (0) | 2023.06.18 |