트리(Tree)

자료구조에는 선형, 비선형 자료구조가 있다.

트리는 이 중에서 비선형 자료구조에 속한다. 특히 계층구조가 있는 가족의

가계도, 회사의 조직도, 컴퓨터의 디렉토리 구조 등의 계층적인 구조를 표

현할 때 사용된다.

---

---

트리의 용어들 :

(1) A는 루트노드.

(2) B는 D와 E의 부모노드.

(3) C는 B의 형제 노드.

(4) D와 E는 B의 자식 노드.

(5) B의 차수는 2. (차수 : 자식 노드의 개수)

(6) 위의 트리의 높이는 3.

(7) 자식 노드가 없는 노드는 단일 노드.

트리의 종류 :

1. 일반 트리 : 자식의 개수가 무한대

2. 이진 트리 : 자식의 개수가 최대 2개.

---

이진 트리

정의 : 공집합이거나 루트와 왼쪽, 오른쪽 서브트리로 구성된 노드들의 유한 집합. 이진트리의 서브트리는 모두 이진트리여야 한다.

n개의 노드를 가진 이진트리는 정확하게 n-1개의 간선을 가진다.

종류

포화 이진 트리 : 각 레벨에 노드가 꽉 차있는 이진트리.

완전 이진 트리 : 높이가 k일 때, 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서 왼쪽부터 오른쪽으로 노드가 순서대로 채워져있는 이진트리.

기타 이진트리 : 이 이외에 이진트리.