- 노드로 이루어진 자료 구조
- 사이클이 없는 그래프
- 계층적인 자료를 표현하는 데 이용되는 자료 구조
| 용어 | 설명 |
|---|---|
| 노드 | 트리의 구성 요소 |
| 부모 노드 | 어떤 원소 바로 위에 연결되어 있는 원소. |
| 자식 노드 | 어떤 원소 바로 아래에 연결되어 있는 원소. |
| 형제 노드 | 같은 부모 노드의 자식들. 자매 노드라고도 한다. |
| 조상 노드 | 어떤 노드보다 위에 위치한 연결된 노드. |
| 후손 노드 | 어떤 노드보다 아래에 위치한 연결된 노드. |
| 루트 노드 | 부모가 없는 노드. |
| 리프 노드 | 자식이 없는 노드. 외부 노드 라고도 한다. |
| 내부 노드 | 리프 노드를 제외한 모든 노드. 즉, 자식이 있는 노드. |
| 차수(degree) | 어떤 노드가 가지고 있는 자식 노드의 개수 |
| 레벨(level) | 트리의 각 층에 번호를 매기는 것. 루트는 1이고 내려갈수록 1씩 증가한다. |
| 높이(height) | 트리가 가지고 있는 최대 레벨 |
- DAG1)의 한 종류이다.
- 간선의 개수는 항상 정점의 개수 - 1이다. (E = V - 1)
- root에서 어떤 노드로 가는 경로는 유일하다.
- 임의의 두 노드 간의 경로가 유일하다. 두 개의 정점 사이에 반드시 1개의 경로만을 가진다.
- 한 개의 루트 노드만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가진다.
-
기본 트리
- root라 불리는 노드를 가지고 있다.
- root가 아닌 모든 노드들은 부모노드를 갖는다.
-
이진 트리
- 모든 노드가 최대 2개까지의 자식 노드를 가지고 있는 트리.
- 왼쪽으로 연결된 노드를 왼쪽 자식이라 한다.
- 오른쪽으로 연결된 노드를 오른쪽 자식이라 한다.
-
인접 배열 이용
- 1차원 배열 이용
- 트리는 부모 노드를 0개(root) 또는 1개를 가진다는 성질을 이용
- 배열 값에 부모노드의 번호를 저장한다.
- 2차원 배열 이용
- 이진 트리 구현시 2차원 배열에 자식 노드를 저장
- a[i][0] : 왼쪽 자식 노드, a[i][1] : 오른쪽 자식 노드
- 1차원 배열 이용
-
인접 리스트 이용