7장 트리 - (1) 트리의 개념 및 트리의 표현

1. 트리(Tree)

- 자료구조의 일종

- 사이클이 없는 그래프

- 정점의 개수 V

- 간선의 개수 V-1 

- 정점의 개수가 V 이고 간선의 개수가 V-1 이면 트리일까? 

  답) NO, 연결되어 있다는 조건이 있어야 트리

2. 루트 있는 트리 (Rooted Tree)

- 루트가 있는 트리

- 아래 그림에서 1번이 루트이다.

- 루트부터 아래로 방향을 정할 수 있다.

1) 부모(Parent)

- 1은 2의 부모, 2는 4의 부모

2) 자식(Children)

- 2는 1의 자식, 4는 2의 자식

- 3의 자식 : 6, 7

3) 단말 정점(Leaf Node)

- 자식이 없는 정점

- 4, 5, 6, 7 

4) 형제(Sibling)

- 같은 부모를 가지면 형제

- 4와 5는 형제

- 6과 7은 형제

- 2와 3도 형제

5) 깊이(Depth; Level)

- 루트에서 부터 거리(아래 처럼 루트의 깊이를 0으로 하는 경우와 1로 하는 경우가 있다.)

6) 높이(Height)

- 깊이 중 가장 큰 값 : 2 또는 3

7) 조상, 자손(Ancestor, Descendent)

- p->q로 갈 수 있을 때,

- p가 q보다 루트에 가까우면

- p는 q의 조상, q는 p의 자손

- 자기 자신이 조상, 자손이 될 수 있음

- 1의 조상은 1, 1의 자손은 2, 3, 4, 5, 6, 7

8) 이진 트리(Binary Tree)

- 자식을 최대 2개만 가지고 있는 트리

 

3. 트리의 표현

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

- 또는

- 트리의 모든 노드는 부모를 하나 또는 0개(루트)만 가지기 때문에 부모만 저장하는 방식으로 저장할 수 있다.

- 부모가 0개인 경우는 트리의 루트인데, 이 경우 부모를 -1이나 0으로 처리

- 이진 트리의 경우에는 배열로 표현할 수 있다. 부모의 노드가 x이면 자식의 노드는 2*x, 2*x+1 로 나타내면 된다.

- 이 경우에, 한 방향으로만 쭉 연결된 이진 트리의 경우, 쓸데 없이 많은 배열 공간을 잡아 먹는다.

- 또는 이진트리의 경우, A[i][0]에 왼쪽 자식, A[i][1]에 오른쪽 자식을 저장할 수 있다.