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

1. 삭제할 노드의 왼쪽 서브 트리에서 키 값이 가장 큰 노드를 검색합니다.
2. 검색한 노드를 삭제 위치로 옮깁니다(검색한 노드의 데이터를 삭제 대상 노드 위치로 복사합니다).
3. 옮긴 노드를 삭제합니다. 이때
• 옮긴 노드에 자식이 없으면
‘자식 노드가 없는 노드의 삭제 순서’에 따라 노드를 삭제합니다.
• 옮긴 노드에 자식이 1개만 있으면
‘자식 노드가 1개 있는 노드의 삭제 순서’에 따라 노드를 삭제합니다.

Remove 함수는 앞에서 배운 세 가지 상태에서 노드를 삭제하는 방법을 구현한 함수입니다.

실습 10-2[D] •완성 파일 chap10/BinTree.c
01 /*--- 노드 삭제 ---*/
02 int Remove (BinNode **root, const Member *x)
03 {
04 BinNode *next *temp;
05 BinNode **left;
06 BinNode **p = root;
07
08 while(1) {
09 int cond;
10 if(*p == NULL) {
11 printf("【오류】 %d는 등록되어 있지 않습니다.\n", x->no);
12 return –1; /* 이 키는 없습니다. */
13 } else if((cond = MemberNocmp(x, &(*p)->data)) == 0)
14 break; /* 검색 성공 */
15 else if(cond < 0)
16 p = &((*p)->left); /* 왼쪽 서브 트리에서 검색 */
17 else
18 p = &((*p)->right); /* 오른쪽 서브 트리에서 검색 */
19 }
20
21 if((*p)->left == NULL)
22 next = (*p)->right;
23 else {
24 left = &((*p)->left);
25 while((*left)->right != NULL)
26 left = &(*left)->right;
27 next = *left;
28 *left = (*left)->left;
29 next->left = (*p)->left;
30 next->right = (*p)->right;

10•트리 421