코딩테스트/Python
[Data Structure] 트리
swwho
2023. 3. 30. 17:04
728x90
반응형
트리 구조
- 계층형 트리 구조를 나타내는 추상 자료형
- 루트, 서브트리로 구성되며, 서로가 연결된 노드의 집합(재귀의 자기참조 형식)
트리 구조 주요 용어
- 차수 : 자식 노드의 개수
- 크기 : 자신을 포함한 모든 자식 노드의 개수
- 높이 : 현재 위치에서 리프노드 까지의 거리
- 깊이 : 루트에서 현재 노드까지의 거리
이진 트리
모든 노드의 차수가 2이하인 트리
- 정 이진트리 (full binary tree) : 모든 노드의 차수가 0또는 2인 트리
- 완전 이진트리 (complete binary tree) : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워진 트리
- 포화 이진트리 (perfect binary tree) : 정이진트리 이면서, 완전이진트리인 경우