(9)실습7주차_이진탐색트리_전위순회,삽입,삭제_이론+코드[문제1]

#문제 PDF 파일 :

알고리즘 및 실습_7주차.pdf

0.26MB

[문제1] :

#알아야 할 개념 (요약) :

• 이진 트리 전위(중위 후위에서도 마찬가지) 순회 메소드 구현에서 if구현 실수 조심
• 이진 탐색 트리의 삽입 메소드와 삭제 메소드는 이중포인터를 매개변수로 한다.
• 이진 탐색 트리의 삭제 메소드 논리 전개(이건 시발 계속해도 까먹음)

1_ 전위 순회 구현 중 L과 R 구현에서 if만 쓰고 else를 쓰지 않도록 한다. 자주하는 실수

//이진 탐색 트리 전위 순회 메소드 D L R
void PrintTree(BTree* tree)
{
    if (tree == NULL) return;
 
    printf(" %d", tree->data);
 
    if (tree->Left != NULL) PrintTree(tree->Left);
    //실수3_else if로 하면 출력 안됨
    if (tree->Right != NULL) PrintTree(tree->Right);
}

2_ 이진탐색트리의 삽입, 삭제 메소드는 트리 구조가 변화하기 때문에, Root노드를 매개변수로 받을 때, 이중포인터로 받는다.

※단일 포인터로도 구현이 가능하긴 하지만, 안전성을 위해, 이중 포인터로 사용한다.(★이 부분 출제하지 모르니 더 조사해보고 포스팅하겠음)

3_★ 이진 탐색 트리 삭제 메소드 논리 순서 노트이론 :

 

 

##전체 코드[문제1] :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#pragma warning (disable : 4996)
 
typedef struct _BSTNode {
    int data;
    struct _BSTNode* Left;
    struct _BSTNode* Right;
}BNode;
 
BNode* SearchBSTree(BNode* tree, int data) 
{
    if (tree == NULL) return NULL;
 
    if (tree->data > data)
    {
        return SearchBSTree(tree->Left, data);
    }
    else if (tree->data < data)
    {
        return SearchBSTree(tree->Right, data);
    }
    else return tree;
 
}
 
void InsertBSTree(BNode** tree, int data) 
{
    if (*tree == NULL) {
 
        *tree = (BNode*)malloc(sizeof(BNode));
        (*tree)->data = data;
        (*tree)->Left = NULL;
        (*tree)->Right = NULL;
 
        return;
    }
 
    if ((*tree)->data > data)
    {
        InsertBSTree(&((*tree)->Left), data);
    }
    else if ((*tree)->data < data)
    {
        InsertBSTree(&((*tree)->Right), data);
    }
    else
    {
        printf("삽입할 data가 이미 트리에 존재합니다.\n");
        return;
    }
 
}
 
void DeleteBSTree(BNode** tree, int data) 
{
    //1_ 재귀함수 종료,예외조건 : 빈자리에 도달 || 처음부터 빈트리 
    //=>삭제할 노드가 트리에 없다는 뜻
    if ((*tree) == NULL) {
        printf("X\n");
        return;
    }
 
    //2_ 탐색 => 재귀 
    if ((*tree)->data > data)
    {
        DeleteBSTree(&((*tree)->Left), data);
    }
    else if ((*tree)->data < data)
    {
        DeleteBSTree(&((*tree)->Right), data);
    }
    else
    {
        //삭제할 노드를 찾았고, (*tree)포인터가 그 노드에 도달 했다면,
        //3_ 삭제할 노드의 data 임시저장
        int del_data = (*tree)->data;
 
        //4_ 삭제할 노드의 자식수 검사
        if ((*tree)->Left == NULL)//삭제할 노드가 0,1차 처리 구현부 
        {
            BNode* tmp = (*tree)->Right;
            free(*tree);
            *tree = tmp;
        }
        else if ((*tree)->Right == NULL) 
        {
            BNode* tmp = (*tree)->Left;
            free(*tree);
            *tree = tmp;
        }
        else//삭제할 노드가 2차인 경우
        {
            BNode* succParent = (*tree);
            BNode* succ = (*tree)->Right;
 
            while (succ->Left!=NULL) 
            {
                succParent = succ;
                succ = succ->Left;
            }
 
 
            //5_ 경우1 경우2 || 경우3 케이스 분류
            if (succParent != (*tree)) 
            {
                succParent->Left = succ->Right;
            }
            else //경우 3
            {
                succParent->Right = succ->Right;
            }
 
            //6_root노드에 succ->data 대입(후계자 계승 작업)
            (*tree)->data = succ->data;
 
            //succ노드를 메모리 해제
            free(succ);
 
            printf("%d\n", del_data);
        }
    }
 
}
 
//전위순회 출력 : //D L R
void PrintTree(BNode* tree) 
{
    if (tree == NULL) return;
 
    printf(" %d", tree->data);
    
    if (tree->Left != NULL) PrintTree(tree->Left);
 
    if (tree->Right != NULL) PrintTree(tree->Right);
}
 
int main() 
{
 
    BNode* BSTree = NULL;
    int input;
    char sign;
 
    while (1) 
    {
        scanf("%c", &sign);
        getchar();
 
        if (sign == 'i') 
        {
            scanf("%d", &input);
 
            getchar();
 
            InsertBSTree(&BSTree, input);
 
        }
        else if (sign == 's')
        {
            BNode* result;
 
            scanf("%d", &input);
 
            getchar();
 
            result = SearchBSTree(BSTree, input);
 
            if (result == NULL) {
                printf("X\n");
            }
            else {
                printf("%d\n", result->data);
            }
        }
        else if (sign == 'd')
        {
            scanf("%d", &input);
 
            getchar();
 
            DeleteBSTree(&BSTree, input);
 
        }
        else if (sign == 'p')
        {
            PrintTree(BSTree);
            printf("\n");
        }
        else if (sign == 'q')
        {
            break;
        }
 
    }
 
    free(BSTree);
 
    return 0;
}