1. 트리란?
- 노드로 구성된 비선형 자료구조로 계층구조를 나타낼 때 사용
- 하나의 루트 노드를 가짐
- 루트 노드는 0개 이상의 자식 노드를 가짐
- 그래프의 한 종류로 사이클을 갖지 않는 그래프
- 나무의 가지처럼 계속 뻗어 나가는 계층구조로 나무를 뒤집은 모습을 생각해보자
- 컴퓨터에서 폴더 안에 폴더와 파일이 있는 구조도 트리 구조
2. 트리 관련 용어
- 간선(Edge): 노드들을 연결하는 선
- 루트 노드(Root Node): 부모 노드가 없는 최상위 노드, 트리는 하나의 루트 노드를 갖는다
- 단말 노드(Leaf Node): 자식이 없는 노드
- 부모 노드(Parent Node): 자식 노드를 갖는 상위 노드
- 자식 노드(Child Node): 부모 노드가 갖는 노드들
- 깊이(depth): 루트 노드에서 특정 노드에 도달하기 위해 거쳐야 하는 간선의 수
- 높이(height): 루트 노드로부터 가장 깊이 있는 노드에 도달하기 위해 거쳐야 하는 간선의 수
- 레벨(level): 트리로부터 특정 노드까지의 깊이
- 크기(size): 자신을 포함한 자손 노드의 개수
- 차수(degree): 특정 노드가 가진 자식 노드의 개수
3. 트리의 특징
- 계층 구조를 나타낼 때 사용된다
- 노드가 N개인 경우 트리는 N-1개의 간선을 가진다
- 루트 노드에서 특정 노드로 가는 경로는 유일하다
- 자식 노드는 하나의 부모 노드만 가진다
- 트리를 순회하는 방법은 전위 순회(Pre-order), 중위 순회(In-order), 후위 순회(Post-order)가 있다
4. 트리의 종류
1) 완전 이진트리(Complete Binary Tree)
- 트리의 모든 높이에서 노드가 꽉 차 있는 이진트리
- 마지막 레벨은 노드가 꽉 차 있지 않아도 되지만 왼쪽에서 오른쪽으로 노드가 채워져 있어야 한다
- 배열을 이용해 표현 가능하다
2) 전 이진트리(Full Binary Tree)
- 모든 노드가 0개 또는 2개의 자식 노드를 갖는 이진트리
3) 포화 이진트리(Perferct Binary Tree)
- 완전 이진트리이면서 전 이진트리인 경우 포화 이진트리라 한다
- 모든 말단 노드가 같은 높이에 있으며 마지막 단계의 노드는 가득 차 있고 자식 노드를 갖지 않는다
- 말단 노드를 제외한 모든 노드는 2개의 자식 노드를 가진다
- 노드의 개수는 정확히 2^n - 1 개이다 (n: 트리의 높이)
'CS > 자료구조' 카테고리의 다른 글
| [자료구조] 힙(Heap) (0) | 2022.03.15 |
|---|---|
| [Python] 트리 구현 / 순회(전위 순회, 중위 순회, 후위 순회, 레벨 순회) (0) | 2022.03.11 |
| [Python] 큐 구현 (0) | 2021.04.24 |
| [Python] 이중 연결리스트 구현 (1) | 2021.04.24 |
| [자료구조] 큐 (Queue) (0) | 2021.04.17 |