트리

- 사이클이 없는 연결 그래프

- 정점의 개수 : V

- 간선의 개수 : V-1

- 모든 정점이 연결되어 있어야 함

---

- 이진 트리

 

- 포화 이진 트리

- 리프 노드를 제외한 노드의 자식의 수 : 2

- 리프 노드의 자식의 수 : 0

- 모든 리프 노드의 깊이가 같아야 함.

- 높이가 h인 토리의 노드 개수 = 2^h - 1

---

- 완전 이진 트리

- 마지막 레벨을 제외한 모든 노드들이 채워져있음. 마지막 레벨 노드들은 가능한 한 왼쪽부터 채워져있는 구조.

---

- 트리는 그래프이기 때문에 그래프의 표현과 같은 방식으로 저장할 수 있음.

- 루트가 있는 트리인 경우, 트리의 모든 노드는 부모를 하나 또는 0개 가지므로 부모만 저장하는 방식으로 저장할 수 있음.

- 트리를 표현하는 방식

1. 배열에 트리의 부모만 저장하는 방식

2. 완전 이진 트리의 경우 배열로 표현 가능. 부모의 노드가 x인 경우에 자식의 노드는 2*x, 2*x+1로 나타냄.

3. 이진 트리의 경우 구조체나 클래스를 이용해서 표현 가능.

---

- 트리를 순회하기 위해서는 BFS, DFS 방법을 사용함.

- DFS의 경우 3가지 출력 순서가 있음.

1. 프리오더

2. 인오더

3. 포스트오더

---

- 트리의 탐색은 DFS/BFS 알고리즘을 이용해서 할 수 있음.

- 트리는 사이클이 없는 그래프이기 때문에, 임의의 두 정점 사이의 경로는 1개임. 따라서, DFS/BFS 알고리즘을 이용해서 최단 거리를 구할 수 있음.

---

- 트리에 존재하는 모든 경로 중에서 가장 긴 것의 길이를 트리의 지름.

- 트리의 지름은 탐색 2번으로 구할 수 있음.

1. 한 정점 s에서 모든 정점까지의 거리를 구함. 이 때, 가장 먼 거리인 정점을 u라고 함.

2. u에서 모든 정점까지의 거리를 구함. 이 때, 가장 먼 거리의 정점 v를 구함.

=> d(u, v)를 u와 v 사이의 거리라고 했을 때, d(u, v)가 트리의 지름.

 

- 또는 포스트 오더를 이용해서도 구할 수 있음.