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

노드를 생성하는 AllocBinNode 함수

AllocBinNode 함수는 BinNode형 객체를 만드는 함수입니다.

노드 멤버의 값을 설정하는 SetBinNode 함수
SetBinNode 함수는 BinNode형 객체의 멤버 값을 설정하는 함수로, 첫 번째 매개변수 n이

가리키는 BinNode형 객체에 대해 멤버의 값을 설정합니다. n이 가리키는 객체 멤버인 data,
left, right에 두 번째 매개변수 x가 가리키는 객체의 값 *x와 세 번째, 네 번째 매개변수의 포
인터 값 left, right를 각각 대입합니다.

비어 있는 상태의 이진검색트리 만들기
해시법과 선형 리스트 프로그램에는 빈 테이블이나 리스트를 만드는 Initialize 함수가 있었
습니다. 하지만 이 프로그램에는 Initialize 함수가 없습니다. 왜냐하면 그림 10-10과 같이

루트 노드를 가리키는 BinNode형 객체를 하나 준비하고 널 값을 대입하면 되기 때문입니다.
이때 루트 노드를 가리키는 포인터는 이진검색트리를 사용하는 실습 10-3의 main 함수에서
미리 선언합니다.

NULL（노드를 가리키는 상태가 아닙니다.）
root
[그림 10-10] 빈 상태의 이진검색트리

키 값으로 검색하는 Search 함수
그림 10-11은 이진검색트리의 검색 과정 중 한 예입니다. a 는 검색에 성공한 경우이고 b 는
검색에 실패한 경우입니다.

검색에 성공한 경우( a )
이진검색트리에서 키 값이 3인 노드를 검색하는 과정은 다음과 같습니다.

1 루트를 선택합니다(5). 3은 5보다 작기 때문에 왼쪽으로 검색을 진행합니다.
2 선택한 노드는 2입니다. 3은 2보다 크기 때문에 오른쪽으로 검색을 진행합니다.
3 선택한 노드는 4입니다. 3은 4보다 작기 때문에 왼쪽으로 검색을 진행합니다.
4 3에 도착해 검색에 성공합니다.

10•트리 413