Page 409 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

10-2 이진트리와 이진검색트리

이번 절에서는 이진트리와 이진검색트리를 살펴보겠습니다.

이진트리

노드가 왼쪽 자식과 오른쪽 자식을 갖는 트리를 이진트리(binary tree)라고 합니다. 이때 각 노
드의 자식은 2명 이하만 유지해야 합니다. 그림 10-6을 보면서 좀 더 자세히 살펴보겠습니다.

A

노드 B의 왼쪽 서브 트리
B C
노드 B의 오른쪽 서브 트리
D E F G

H I J K L

[그림 10-6] 이진트리

이진트리의 특징은 왼쪽 자식과 오른쪽 자식을 구분한다는 점입니다. 예를 들어 그림 10-6에
서 노드 B의 왼쪽 자식은 D, 오른쪽 자식은 E입니다. 이때 왼쪽 자식을 다시 루트로 하는 서브
트리를 왼쪽 서브 트리(left subtree), 오른쪽 자식을 다시 루트로 하는 서브 트리를 오른쪽 서

브 트리(right subtree)라고 합니다. 초록색으로 표시한 부분이 B의 왼쪽 서브 트리, 회색으로
표시한 부분이 B의 오른쪽 서브 트리입니다.

완전이진트리
루트부터 노드가 채워져 있으면서 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 채워져 있
는 이진트리를 완전이진트리(complete binary tree)라고 합니다. 그림 10-7을 보면서 ‘채우다’

라는 말의 의미와 함께 좀 더 자세히 살펴보겠습니다.

1. 마지막 레벨을 제외한 레벨은 노드를 가득 채웁니다.
2. 마지막 레벨은 왼쪽부터 오른쪽 방향으로 노드를 채우되 반드시 끝까지 채울 필요는 없습니다.

10•트리 409