[자료구조] 이진트리(Binary Tree)

이진트리(Binary Tree)란?

한 노드가 최대 두 개의 자식 노드를 가지는 트리를 말한다. 첫 번째 노드를 부모 노드라고 하며 자식 노드는 왼쪽(left)과 오른쪽(right)으로 불린다.

방향 간선(directed edge) : 부모에서 자식으로 가는 경로(그림의 화살표 부분)

루트 노드(root node) : 부모가 없는 노드. 트리는 하나의 루트 노드만을 가진다.

단말 노드(leaf node) : 자식이 없는 노드

깊이(depth) : 루트 노드에서 자신까지 가는 경로의 길이

레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합. 루트 노드의 깊이는 0이다.

높이(height) : 루트 노드에서 가장 깊이 있는 노드까지 가는 경로의 길이. 루트 노드만 있는 트리의 높이는 0이다.

형제(sibling) : 같은 부모를 가지는 노드

크기(size) : 자신을 포함한 모든 자손 노드의 개수이다.

진입차수(In-degree) : 노드에 들어오는 모든 간선의 수이다.

진출차수(Out-degree) : 노드에서 나가는 모든 간선의 수이다.

이진트리의 종류

1) 사향 이진트리(Skewed Binary Tree)

루트를 제외한 모든 노드가 부모 노드의 왼쪽노드이거나 또는 오른쪽노드인 이진 트리

 

2) 포화 이진트리(Full Binary Tree)

트리의 높이까지 모든 노드가 가득찬 트리이다. 높이가 1이면 루트 하나만 있으므로 노드 개수는 1개이며 높이가 2이면 루트와 양쪽 자식을 합쳐 세 개의 노드가 존재한다. 높이가 3이면 7개, 4이면 15개이며 일반적으로 높이가 n인 포화 이진 트리의 노드 개수는 2ⁿ-1개이다.

3) 완전 이진트리(Complete Binary Tree)

임의의 두 잎 노드의 레벨의 차이가 1 이하이며 왼쪽에서 오른쪽으로 채워진 이진 트리