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

그림 10-7과 같이 완전이진트리에서 너비 우선 탐색을 하며 각 노드에 0, 1, 2, … 값을 주면

배열에 저장하는 인덱스와 일대일로 대응한다는 것을 알 수 있습니다.

0
마지막 레벨이 아니라면 노드
1 2 를 가득 채웁니다.

3 4 5 6

마지막 레벨은 왼쪽부터 노드
7 8 9 10 11
를 채우기만 하면 됩니다.
[그림 10-7] 완전이진트리

k+1
높이가 k인 완전이진트리가 가질 수 있는 노드의 최댓값은 2 – 1개입니다. 따라서 n개의 노
드를 저장할 수 있는 완전이진트리의 높이는 log n입니다.
완전이진트리는 06장의 힙 정렬에 사용했습니다.

이진검색트리
이진검색트리(binary Search tree)는 이진트리가 다음 조건을 만족하면 됩니다.

1. 어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값보다 작아야 합니다.
2. 오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 커야 합니다.
3. 같은 키 값을 갖는 노드는 없습니다.

그림 10-8은 이진검색트리를 구현한 예입니다. 여기서 노드 11

5를 보면 왼쪽 서브 트리 노드(4, 1)는 모두 5보다 작습니다. 5 15
그리고 오른쪽 서브 트리 노드(7, 6, 9)는 모두 5보다 큽니다. 4 7 13 18
이때 이진검색트리를 중위 순회(Inorder)하면 다음과 같이 키
1 6 9 12 14
값의 오름차순으로 노드를 얻을 수 있습니다.
[그림 10-8] 이진검색트리의 구현

1  4  5  6  7  9  11  12  13  14  15  18

이와 같이 이진검색트리는 중위 순회를 하면 키 값의 오름차순으로 노드를 얻을 수 있다는 점
과 구조가 단순하다는 점, 이진검색과 비슷한 방식으로 검색이 가능하다는 점, 노드의 삽입이

410 C 알고리즘