1. 이진트리(Binary Tree)란?

이진 트리는 모든 노드가 정확하게 두 개의 서브트리를 가지고 있는 트리이다. 다만 서브트리는 공백이 될 수 있다. 즉 노드의 유한 집합으로서 공백이거나 루트와 두 개의 분리된 이진트리인 경우 왼쪽서브트리와 오른쪽 서브트리로 구성된다. 여기서 중요한점은 왼쪽과 오른쪽 서브트리를 확실하게 구분한다는 것이다.

이 이진트리에서 두개의 서브 트리가 모두 공백인 리프 노드들은 D, H, F. I이고 노드 E, G는 공백이 아닌 서버트리를 하나씩 가지고 있다. 노드 E는 공백 왼쪽 서브트리와 오른쪽 서브트리 H를 가지고 있으며 노드 G는 왼쪽 서브트리 I와 오른쪽 공백 서브트리를 가지고 있다.
위에 설명중 왼쪽 서브트리와 오른쪽 서브트리를 확실하게 구분한다고 하였다. 아래 그림은 두개의 트리인데 일반적인 트리에서 두개의 트리는 같지만 이진 트리에서는 두개의 트리는 다른 트리이다. 이는 이진트리에서는 서브트리의 위치가 다르기 때문이다.

2. 이진트리의 종류

1. 편향 이진트리(Skewed Binary Tree)

편향 이진트리란 모든 노드가 부모의 왼쪽 자식이기 때문에 왼편으로 편향됭 있거나 반대로 모든 노드가 부모의 오른쪽 자식으로 되어 오른쪽으로 편향되어 있어야 한다.

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

포화 이진트리란 이진트리가 보유할 수 있는 최대의 노드를 가지고 있는 형태이다. 높이가 h인 이진 트리에서 있을 수 있는 최대 노드 수는 2^h+1 - 1이다. 아래 그림은 높이가 2인 포화 이진트리이다.

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

높이가 h이고 노드 수가 n, 일때 n<=(2^h+1 - 1)인 이진트리를 노드의 레벨 순수에 따라 노드 번호를 붙인다면 이때 각 노드 번호의 위치가 포화 이진트리 번호 1에서 n까지의 위치와 모두 정확하게 일치한다면 이 트리를 완전 이진트리라고 한다. 즉 루트 노드를 1이라고 하고 그외에 모든 노드가 왼쪽에서부터 오른쪽까지 꽉 차서 노드의 수가 n<=(2^h+1 - 1)라면 완전 이진트리이다. 아래 그림은 완전 이진트리의 예이다.

3. 이진트리의 표현

1. 순차표현

이진 트리는 유일하게 붙여지는 포화 이진 트리 번호를 이용하면 순차 표현 즉 1차원 배열로 쉽게 표현할 수 있다. 즉 포화 이진트리 번호를 배열의 인덱스로 사용하면 된다. 아래 그림은 이진 트리의 순차표현을 보여준다. 이때 1차원 배열에시 인덱스 0은 실제 사용하지 않고 인덱스 1은 항상 루트 노드를 나타낸다.


n개의 노드를 가진 이진트리를 1차원 배열로 표현했을 때 포화 이진트리 번호를 인덱스로 사용하면 어떤 노드 i의 부모, 왼쪽자식, 오른쪽 자식의 인덱스를 쉽게 알 수 있다. 아래 표는 완전 이진트리를 표현한 1차원 배열에서 인덱스 관계이다.

목표 노드	인덱스 값	조건
노드 i의 부모	i/2	i > 1
노드 i의 왼쪽 자식	2 * i	2 * i <= n
노드 i의 오른쪽 자식	2 * i + 1	(2 * i + 1) <= n
루트 노드	1	0 < n

이진트리의 순차표현은 어떠한 이진 트리의 표현에도 적용할 수 있다는 장점이 있다. 하지만 단점으로 저장공간을 효율적으로 사용하지 못할 수 있다는 단점이 있다. 그 예가 위에 편향 이진트리이다. 또한 트리의 중간에 삭제와 삽입을 하게 될 경우 많은 노드들의 이동이 불가피 하게 된다.

2. 연결 표현

순차 표현의 문제 때문에 대부분의 경우에는 순차 표현보다는 연결 표현을 사용하고 있다. 이 연결표현을 위해서는 각 노드들을 다음 그림과 같이 left, data, right를 포함하는 구조를 가지고 있다. 여기서 필드 left, right는 각각 왼쪽 서브트리와 오른쪽 서브트리를 가리키는 링크이다. 이 노드 구조는 부모 노드를 찾기가 어렵다는 문제점이 있지만 꼭 필요한 경우에는 parent 필드를 추가해서 사용하면 된다.

아래 그림은 완전이진 트리를 연결 표현으로 나타낸 것이다. 여기서 left와 right는 왼쪽 서브트리와, 오른쪽 서브트리를 가리키는 포인터 필드가 되며 만일 서브트리가 공백이면 해당 노드는 null이된다.

이러한 노드의 포인터 표현을 java에서하면 아래 소스코드처럼 만들 수 있다.

class Node{
	char data;
	Node left;
	Node right;
}