(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)
 
//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;
}