[CS] What is Binary Trees? (이진 트리)

이진트리란 무엇인가?

이진 트리는 각각의 노드에 최대 두 개의 자식 노드를 갖는 트리 형태의 자료 구조다.

이 때 두 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 구분한다.

이진 트리의 최상위 노드를 루트 노드(Root node)라고 한다.

 

[이미지] 이진트리 설명

 

 

이진 트리의 특징

 

1. 각 노드는 최대 두 개의 자식 노드를 가질 수 있다.

[이미지] 이진트리 노드는 최대 2개까지다.

2. 이진 트리는 재귀적(Recursive)인 특징이 있으며 이는 각각의 서브트리 역시 이진 트리의 성질을 띤다.

[이미지] A노드에 B,E노드가 있고 B노드에 C,D가 있는 형태로 계속 반복될 수 있다.

3. 높이가 h인 이진트리가 가질 수 있는 노드의 최소 갯수는 h개이다.

[이미지] 높이가 3인 이진트리의 노드가 최소가 되는 값은 3이다.

4. 높이가  h인 이진트리가 가질 수 있는 노드의 최대 갯수는 2^h - 1개 이다.

높이가 3인 이진트리의 노드가 최대가 되는 값은 2^3 - 1 = 7이다.

 

이진트리의 종류

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

완전 이진트리는 모든 레벨이 꽉 차 있고 마지막 레벨만은 오른쪽부터 차례대로 비어있을 수 있는 이진트리를 말한다.

[이미지] 완전 이진트리의 예

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

모든 노드가 0개 혹은 2개의 자식 노드를 가진 이진 트리다.

즉, 자식 노드가 하나만 있는 노드는 없다.

[이미지] 포화 이진트리 예시

3. 기타 이진트리

위 두가지 특성을 제외하고 이진트리의 성질을 만족한다면 기타 이진트리라고 한다.

이진트리의 탐색

 

1. 전위 순회(Preorder Traversal) : 루트 -> 왼쪽 -> 오른쪽 순으로 탐색한다.

[이미지] 전위 순회 A-B-C-D-E-F-G 순으로 순회한다.

2. 중위 순회(Inorder Traversal) : 왼쪽 -> 루트 -> 오른쪽 순으로 탐색한다.

[이미지] 중위 순회 C-B-D-A-F-E-G 순으로 순회한다.

3. 후위 순회(Postorder Traversal) : 왼쪽 > 오른 쪽 -> 루트 순으로 탐색한다.

[이미지] 후위 순회 C-D-B-F-G-E-A순으로 순회한다.