[부록]실습7주차_BST검색,삽입,삭제_[문제1]_2차시도

＠100점 안나오길래, 다시 작성 후, 다시 공부함 ㅅㅂ

 

#구조체 :

#트리에 노드 메모리 할당 메소드 :

#검색 메소드 :

• 매개변수가 일중 포인터일 떄, 반환값이 노드포인터이므로 => "return Search(p->left||p->right)" 로 재귀 호출한다.

#삽입 메소드 :

• 삽입 메소드의 매개인자는 이중 포인터이므로,

1_ 반환형 : void

2_ 재귀 호출시 , 매개인자를 &연산자로 호출

#삭제 메소드 :

• 삭제메소드도 매개인자 마찬가지로 이중포인터이고,
• 삭제대상이 0차, 1차, 2차일 때,

1_ 0차일 때, => free(삭제대상) => 삭제대상에 NULL 대입

2_ 1차일 때, => NULL이 아닌 자손 노드에 tmp 임시 보관 => free(삭제대상) => (*삭제대상)에 tmp 대입

3_★ 2차일 때, => ↘↙(FindMin) 찾아 tmp 보관 => (*삭제대상 노드)에 tmp->data 대입 => 다시 (*삭제대상)노드의 right부터 tmp노드의 data 재귀호출로 tmp를 삭제한다. 

# 전위순회 BST출력 메소드 :

# 후위 순회 트리 메모리 해제 메소드 :

 

# 전체 코드 :

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#pragma warning (disable : 4996)
 
//BST트리 구조체
typedef struct _BSTtee {
    struct _BSTtee* left;
    struct _BSTtee* right;
    int data;
}Node;
 
//노드 메모리할당 메소드
Node* CreateNode(int data) 
{
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
 
    return newNode;
}
 
//BST search메소드
Node* SearchBST(Node* p, int data) 
{
    if (p == NULL) 
    {
        return p;
    }
 
    if (p->data > data) 
    {
        return SearchBST(p->left, data);
    }
    else if (p->data < data) 
    {
        return SearchBST(p->right, data);
    }
    else {
        return p;
    }
}
 
//BST Insert메소드
void InsertBST(Node** p , int data) 
{
    if ((*p) == NULL) 
    {
        (*p) = CreateNode(data);
        return;
    }
 
    if ((*p)->data > data) 
    {
        InsertBST(&((*p)->left), data);
    }
    else if ((*p)->data<data) 
    {
        InsertBST(&((*p)->right), data);
    }
    else 
    {
        printf("중복\n");
        return;
    }
}
 
//BST Delete메소드
 
Node* FindMin(Node* p) {
    Node* tmp = p->right;
    while (tmp->left!=NULL) 
    {
        tmp = tmp->left;
    }
 
    return tmp;
}
 
void DeleteBST(Node** p, int data) 
{
    if ((*p) == NULL) 
    {
        return;
    }
 
    if ((*p)->data > data) {
        DeleteBST(&((*p)->left), data);
    }
    else if ((*p)->data < data) {
        DeleteBST(&((*p)->right), data);
    }
    else 
    {
        if ((*p)->left == NULL && (*p)->right == NULL) 
        {
            free(*p);
            (*p) = NULL;
        }
        else if ((*p)->left == NULL) 
        {
            Node* tmp = (*p)->right;
            free(*p);
            (*p) = tmp;
        }
        else if ((*p)->right == NULL) 
        {
            Node* tmp = (*p)->left;
            free(*p);
            (*p) = tmp;
        }
        else 
        {
            Node* tmp = FindMin((*p));
            (*p)->data = tmp->data;
            DeleteBST(&((*p)->right), tmp->data);
        }
    }
}
 
void PreOrder(Node* p) //D L R
{
    if (p == NULL) return;
 
    printf(" %d", p->data);
 
    if (p->left != NULL)PreOrder(p->left);
    if (p->right != NULL)PreOrder(p->right);
}
 
void FreeTree(Node* p) //L R D
{
 
    if (p == NULL) return;
 
    if (p->left != NULL)FreeTree(p->left);
    if (p->right != NULL)FreeTree(p->right);
 
    free(p);
}
 
int main() 
{
    Node* root = NULL;
    char command;
    int key;
 
    while (1) 
    {
        scanf("%c", &command);
 
        if (command == 'i')
        {
            scanf("%d", &key);
            getchar();
            InsertBST(&root, key);
 
        }
        else if (command == 'd')
        {
            scanf("%d", &key);
            getchar();
            Node* search = SearchBST(root, key);
            if (search != NULL) {
                printf("%d\n", search->data);
                DeleteBST(&root, key);
            }
            else {
                printf("X\n");
            }
        }
        else if (command == 's')
        {
            scanf("%d", &key);
            getchar();
            Node* search = SearchBST(root, key);
            if (search != NULL) {
                printf("%d\n", search->data);
            }
            else {
                printf("X\n");
            }
 
        }
        else if (command == 'p')
        {
            PreOrder(root);
            printf("\n");
        }
        else if (command == 'q')
        {
            FreeTree(root);
            break;
        }
    }
 
    return 0;
}