[자료구조] 트리(Tree)

1. 트리란?

- 노드로 구성된 비선형 자료구조로 계층구조를 나타낼 때 사용

- 하나의 루트 노드를 가짐

- 루트 노드는 0개 이상의 자식 노드를 가짐

- 그래프의 한 종류로 사이클을 갖지 않는 그래프

- 나무의 가지처럼 계속 뻗어 나가는 계층구조로 나무를 뒤집은 모습을 생각해보자

- 컴퓨터에서 폴더 안에 폴더와 파일이 있는 구조도 트리 구조

2개의 자식노드를 갖는 루트노드

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: 트리의 높이)