[자료구조 C 언어] C 프로그래밍 자료구조 - 11 : 트리, 이진 트리의 개념 (Tree, Binary Tree)

1. 트리

 

계층적 구조의 자료를 표현할 때 사용한다.

 

1-1 트리의 정의

 

- 하나 이상의 노드로 이루어진 유한집합

- Root라고 하는 노드가 하나 존재

- 나머지 노드들은 n (>= 0)개의 집합 T1, T2, ..., Tn으로 분할

  -> Tn : 분리된 트리 (Root의 서브 트리)

 

 

1-2 트리에 관련된 용어들

- 노드의 차수(degree) (A: 3): 특정 노드 하위에 노드가 몇 단계 있는지

- 트리의 차수(degree) (3): Root 노드 하위에 노드가 몇 단계 있는지

- 단말 노드(leaf of terminal node): 각 노드의 가장 하위 노드

- 부모 노드(E: B), 자식 노드(B: E & F), 형제 노드(E&F): 각 노드의 관계

- 조상 노드(M: H. D, A), 자손 노드(B: E, F, K, L)

- Level (Root: 1), 높이 또는 깊이 (4)

 

 

2. 이진 트리 (binary tree)

 

- 모든 노드의 차수 (degree)가 2를 넘지 않는 트리

  -> 일반 트리에 비해 구현 용이

 

- 왼쪽 서브 트리와 오른쪽 서브 트리가 구분

 

2-1 이진 트리의 정의

 

- 유한 개의 노드들의 집합

- 노드 수는 0개가 될 수 있음

- 하나의 root 노드와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성

- 각 서브 트리는 다시 이진 트리

 

 

2-2 트리를 이진 트리로 변환하는 방법

 

- Left Child - Right Sibling 표현

  1) 노드 A의 제일 왼쪽 노드 => A의 왼쪽 자식 노드

  2) A의 나머지 자식 노드들 => 자식 노드의 오른족 자식

 

* 중요한 점은 한 노드의 자식 노드들 부터 차례로 정리해야 합니다.

  -> A의 자식 노드 정리하고, B의 자식 노드 정리하고, ...

 

 

2-3 이진 트리의 성질

 

- 최대 노드 수

 

1) 이진 트리의 레벨 i에서 최대 노드 수는 2^(i-1) (i >= 1)

2) 깊이가 k인 이진 트리가 가질 수 있는 최대 노드 수 = 

- 단말 노드 수와 차수가 2인 노드 수

 

1) n0: 단말 노드 수, n2: 차수가 2인 노드의 수

2) n0 = n2 + 1

  -> n = n0 + n1 + n2 & n = E (선의 수) + 1 = n1 + 2n2 + 1

 

- 포화 이진 트리 (full binary tree): 깊이가 k이고, 노드 수가 2^(k) - 1 (k >= 0)인 이진 트리

 

 

2-4 완전 이진 트리 (Complete Binary Tree)

2-4-1 완전 이진 트리의 정의

 

깊이가 k이고 노드 수가 n인 이진 트리의 각 노드들이 

 

깊이가 k인 포화 이진 트리에서 1부터 n까지 번호를 붙인 노드들과 

 

1대 1로 일치하는 이진 트리

 

 

2-5 이진 트리의 예

 

3 이진 트리의 표현

 

 

3-1 배열 표현법

 

1차원 배열에 트리를 저장한다.

 

1) 루트 노드는 [1]에 저장

2) 부모 노드가 [i]에 저장될 경우,

2-1) 왼쪽 자식 노드는 [2*i]에 저장

2-1) 오른쪽 자식 노드는 [2*i + 1]에 저장

 

3-1-2 배열 표현의 예

 

3-2 링크 표현법

 

노드를 구조체로 표현

이중 연결리스트와 비슷한 형태를 가집니다.

3-2-1 링크 표현의 예