가라멜의 달달한 세상 탐방

1. 트리

- 검색의 편리함

- 논리적 계층

- 계급적 특성

2. 용어와 논리적 방법

- 트리의 구성

- 노드 : 트리의 항목; 트리에 저장되는 데이터의 묶음

- 부모노드-자식노드 : 상하 계층구조가 있고 직접적으로 연결된 노드로서 상위계층의 부모 노드와 하위계층의 자식 노드

- 루트노드 : 트리의 최상위 노드(부모가 없는 노드)

- 서브트리 : 부모 노드를 삭제하면 생기는 트리들

- 리프 노드 : 트리의 맨 끝(바닥)에 있으면서, 자신의 서브트리를 갖지 않는 노드

- 진입/진출 차수

- 루트 노드 : 진입차수 = 0

- 루트를 제외한 모든 노드의 진입 차수 : 1

- 리프 노드 : 진출 차수 = 0

3. 이진 트리

<정의>

- 모든 노드의 차수가 2 이하인 트리

- 수학적으로 이진트리의 구성에 관한 이론을 정리하기 쉽고, 컴퓨터 내부에서 구현하기도 쉬움

- 모든 노드가 2개 이하의 자식을 가지므로 일반성을 잃지 않고 '오른쪽', '왼쪽' 이라는 방향 개념을 부여할 수도 있음

<완전 이진 트리>

- 이진 트리에서 각 레벨에서 허용되는 최대개수 노드를 가지는 트리

<포화 이진 트리>

- 높이가 k인 이진트리가 '0레벨' 부터 'k-2'까지 다 채우고 마지막 'k-1'레벨에서 왼쪽부터 오른쪽으로 노드들이 차례로 채워진 이진트리

4. 이진 트리의 구현