(13)[Chapter6]이진 탐색 트리_삭제 메소드_비재귀/재귀(이론 + 코드)

##이진탐색트리_삭제_메소드_이론 :

##이진탐색트리_삭제_메소드_비재귀,삭제_이론 + 코드 :

 

##이진탐색트리_삭제_메소드_재귀,삭제_이론 + 코드 :

##자주 햇갈리는 개념 :

★삭제 대상 노드의 자식이 2명인 경우 :

1_ succ_parent 자손 지정

• succ_parent가 움직였을 경우 => succ_parent의 왼쪽자손을 succ의 오른쪽자손으로 업데이트
• succ_parent가 움직이지 않았을 경우 => succ_parent의 오른쪽 자손을 succ의 오른쪽자손으로 업데이트

2_ 다른 Case와 다르게 삭제 대상 노드의 자식이 2명인 경우는 *root노드를 지우는 것이 아닌 succ노드를 지우는 것

##전체 코드 :

#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable : 4996)
 
// 이진트리 구조체
typedef struct _BSTNode {
    struct _BSTNode* left;
    struct _BSTNode* right;
    int data;
} BNode;
 
// 탐색 : 재귀
BNode* SearchBST(BNode* root, int data) {
    // 종료조건
    if (root == NULL) {
        printf("%d은 이진트리탐색에 존재하지 않습니다.\n", data);
        return root;
    }
 
    if (root->data > data) {
        // 왼쪽 재귀
        return SearchBST(root->left, data);
    }
    else if (root->data < data) {
        // 오른쪽 재귀
        return SearchBST(root->right, data);
    }
    else return root;
}
 
// 삽입 : 재귀
void InsertBST(BNode** root, int data) {
    // ★삽입 메소드는 재귀지만, 종료조건이 없음
 
    // 1_ 빈트리에 삽입한다면,
    if (*root == NULL) {
        *root = (BNode*)malloc(sizeof(BNode));
        (*root)->data = data;
        (*root)->left = NULL;
        (*root)->right = NULL;
        return;
    }
 
    // 2_ 빈트리가 아니리면, 탐색(data가 들어갈 자리) , 빈자리시 삽입
    if ((*root)->data > data) { // 왼쪽으로 탐색
        InsertBST(&((*root)->left), data);
    }
    else if ((*root)->data < data) { // 오른쪽으로 탐색
        InsertBST(&((*root)->right), data);
    }
    else {
        printf("%d가 이미 트리안에 중복값으로 존재합니다.\n", data);
        return;
    }
}
 
// 재귀적으로 노드 삭제 함수
void DeleteBSTRec(BNode** root, int data) {
    if (*root == NULL) {
        printf("삭제할 값이 트리에 존재하지 않습니다.\n");
        return;
    }
 
    if (data < (*root)->data) {
        DeleteBSTRec(&((*root)->left), data);
    }
    else if (data > (*root)->data) {
        DeleteBSTRec(&((*root)->right), data);
    }
    else {
        if ((*root)->left == NULL) {
            BNode* temp = (*root)->right;
            free(*root);
            *root = temp;
        }
        else if ((*root)->right == NULL) {
            BNode* temp = (*root)->left;
            free(*root);
            *root = temp;
        }
        else {
            BNode* succParent = *root;
            BNode* succ = (*root)->right;
 
            while (succ->left != NULL) {
                succParent = succ;
                succ = succ->left;
            }
 
            if (succParent != *root) {
                succParent->left = succ->right;
            }
            else {
                succParent->right = succ->right;
            }
 
            (*root)->data = succ->data;
            free(succ);
        }
    }
}
 
// 이진 탐색 트리 출력 (중위 순회 하면, 오름차순 출력)
void InOrder(BNode* root) {
    if (root == NULL) return;
 
    // L
    if (root->left != NULL) InOrder(root->left);
 
    // D
    printf(" %d", root->data);
 
    // R
    if (root->right != NULL) InOrder(root->right);
}
 
int main() {
    BNode* Tree1 = NULL;
 
    InsertBST(&Tree1, 23);
    InsertBST(&Tree1, 11);
    InsertBST(&Tree1, 1);
    InsertBST(&Tree1, 139);
    InsertBST(&Tree1, 67);
 
    InOrder(Tree1);
    printf("\n");
 
    DeleteBSTRec(&Tree1, 23);
    DeleteBSTRec(&Tree1, 11);
    DeleteBSTRec(&Tree1, 9);
 
    InOrder(Tree1);
    printf("\n");
 
    return 0;
}