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

이진검색트리에 노드 1을 삽입하는 과정이 a , 노드 1을 삽입한 이진검색트리에 노드 5를 삽

입하는 과정이 b 입니다.

a 1을 삽입하는 과정 b 5를 삽입하는 과정
검색하는 방법과 마찬가지로 삽입할 위치를 검색하는 방법과 마찬가지로 삽입할 위치를
찾습니다. 추가할 값인 1은 2보다 작고, 2의 찾습니다. 추가할 값인 5는 4보다 크고, 4의
왼쪽 자식 노드는 비어 있으므로 해당 위치를 오른쪽 자식 노드는 비어 있으므로 해당 위치
삽입 위치로 선택합니다. 를 삽입 위치로 선택합니다.
6 6
2 7 2 7
4 1 4

2의 왼쪽 자식 노드로 1을 삽입합니다. 4의 오른쪽 자식 노드로 5를 삽입합니다.

6 6
2 7 2 7
1 4 1 4
5

[그림 10-12] 이진검색트리에 노드를 삽입하는 과정

p를 루트로 하는 이진검색트리에 키 값이 key인 데이터를 삽입하는 알고리즘은 다음과 같습

니다(p는 널이 아닙니다).

1. p에 루트 포인터를 대입합니다(루트를 선택합니다).
2. 삽입할 키 key와 p의 키 값을 비교합니다. 값이 같다면 삽입에 실패합니다(종료).
•값이 같지 않은 경우 key 값이 삽입할 값보다 작으면
왼쪽 자식 노드가 없는 경우에는( a ) 노드를 삽입합니다(종료).
왼쪽 자식 노드가 있는 경우에는 선택한 노드에 왼쪽 자식 노드 포인터를 대입합니다.
•key 값이 삽입할 값보다 크면
오른쪽 자식 노드가 없는 경우에는( b ) 노드를 삽입합니다(종료).
오른쪽 자식 노드가 있는 경우에는 선택한 노드에 오른쪽 자식 노드 포인터를 대입합니다.
3. 2로 되돌아갑니다.

Add 함수는 이 알고리즘을 바탕으로 노드를 삽입합니다.

실습 10-2[C] •완성 파일 chap10/BinTree.c
01 /*--- 노드 삽입 ---*/
02 BinNode *Add (BinNode *p, const Member *x)
03 {

416 C 알고리즘