[C언어 자료구조] 6.3 이진 탐색 트리 소스 코드

[C언어 자료구조] 6.3 이진 탐색 트리 소스 코드

---

 테스트 로직을 구현합시다.

 

 테스트 로직은 단순히 이진 탐색 트리를 생성한 후에 다양한 도서 정보를 추가하고 검색과 삭제 기능 등을 호출하여 잘 동작하는지 확인하는 것입니다.

 

 이 부분에 관한 별도의 설명은 생략할게요.

 

//common.h

#pragma once //헤더 파일을 한 번만 포함해서 컴파일

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#include <string.h>

#include <malloc.h>

#include <memory.h>

#include <time.h>

#pragma warning(disable:4996) //4996컴파일 경고 메시지 출력 해제

 

//Book.h

#pragma once

#include "common.h"

#define MAX_TIT_LEN     200

#define MAX_AUT_LEN 20

typedef struct _Book Book;

struct _Book

{

    char title[MAX_TIT_LEN+1];

    char author[MAX_AUT_LEN+1];

    int num;

};

 

Book *New_Book(const char *title,const char *author,int num);

void Delete_Book(Book *book);

void Book_View(Book *book);

int Book_CompareTitle(Book *book,const char *title);

int Book_CompareAuthor(Book *book,const char *author);

int Book_CompareNum(Book *book,int num);

 

//Book.c

#include "Book.h"

 

void Book_Book(Book *book,const char *title,const char *author,int num);

Book *New_Book(const char *title,const char *author,int num)

{

        Book *book = 0;

        book = (Book *)malloc(sizeof(Book));

        Book_Book(book,title,author,num);

        return book;

}

void Book_Book(Book *book,const char *title,const char *author,int num)

{

        memset(book,0,sizeof(Book));

        strncpy(book->title,title,MAX_TIT_LEN);

        strncpy(book->author,author,MAX_AUT_LEN);

        book->num = num;

}

void Delete_Book(Book *book)

{

        free(book);

}

void Book_View(Book *book)

{

        printf("<%010d>:<%s>\n",book->num,book->title);

        printf("\t 저자:%s\n",book->author);

}

int Book_CompareTitle(Book *book,const char *title)

{

        return strcmp(book->title,title);

}

int Book_CompareAuthor(Book *book,const char *author)

{

        return strcmp(book->author,author);

}

int Book_CompareNum(Book *book,int num)

{

        return book->num-num;

}

 

//BinSearchTree.h

#pragma once

 

#include "Book.h"

typedef struct _Node Node;

struct _Node

{

    Book *book;

    Node *lch;

    Node *rch;

    Node *pa;

};

 

Node *New_Node(Book *data);

typedef struct _BinSearchTree BST;

struct _BinSearchTree

{

    Node *root;

    int count;

};

BST *New_BST();

void Delete_BST(BST *bst);

int BST_Insert(BST *bst,Book *book);

int BST_Remove(BST *bst, int num);

Book *BST_Find(BST *bst, int num);

void BST_List(BST *bst);

 

//BinSearchTree.c

#include "BinSearchTree.h"

#include <malloc.h>

Node *New_Node(Book *data)

{

    Node *node = 0;

    node = (Node *)malloc(sizeof(Node));

    node->book = data;

    node->lch = node->rch = node->pa = 0;

    return node;

}

 

BST *New_BST()

{

    BST *bst = 0;

    bst = (BST *)malloc(sizeof(BST));

    bst->root = 0;

    bst->count = 0;

    return bst;

}

 

void BST_PostOrder(Node *sr);

void Delete_BST(BST *bst)

{

    BST_PostOrder(bst->root);

    free(bst);

}

void BST_PostOrder(Node *sr)

{

    if(sr)

    {

        BST_PostOrder(sr->lch);

        BST_PostOrder(sr->rch);

        Delete_Book(sr->book);

        free(sr);

    }

}

 

Node *BST_FindSeat(Node *sr,int num);

int BST_Insert(BST *bst,Book *book)

{

    Node *parent = 0;

    parent = BST_FindSeat(bst->root,book->num);

    if(parent)

    {

        Node *node = 0;

        int gap = parent->book->num - book->num;

        if( gap == 0)

        {

            return 0;

        }

       

        node = New_Node(book);

        node->pa = parent;

        if(gap>0)

        {

            parent->lch = node;

        }

        else

        {

            parent->rch = node;

        }

    }

    else

    {

        bst->root = New_Node(book);

    }

    bst->count++;

    return 1;

}

Node *BST_FindSeat(Node *sr,int num)

{

    int gap = 0;

    if(sr==0)

    {

        return 0;

    }

    gap = sr->book->num - num;

    if(gap == 0)

    {

        return sr;

    }

    if(gap>0)

    {

        if(sr->lch)

        {

            return BST_FindSeat(sr->lch,num);

        }

        return sr;

    }

    if(sr->rch)

    {

        return BST_FindSeat(sr->rch,num);

    }

    return sr;

}

void BST_Disconnect(BST *bst,Node *node);

int BST_Remove(BST *bst, int num)

{

    Node *node = 0;

    node = BST_FindSeat(bst->root,num);

    if(node)

    {

        if(node->book->num == num)

        {

            BST_Disconnect(bst,node);

            free(node);

            bst->count--;

            return 1;

        }

    }

    return 0;  

}

Node *BST_Change(Node *node);

void BST_Disconnect(BST *bst,Node *node)

{

    Node *pa=0;

    Node *ch=0;

    if(node->lch && node->rch)

    {

        node = BST_Change(node);

    }

    pa = node->pa;

    (ch = node->lch)||(ch = node->rch);

   

    if(pa)

    {

        ch->pa = pa;

    }

    else

    {

        bst->root = ch;

    }

    if(ch)

    {

        if(pa->lch == node)

        {

            pa->lch = ch;

        }

        else

        {

            pa->rch = ch;

        }

    }

}

Node *BST_Change(Node *node)

{

    Node *temp = node;

    while(temp->rch)

    {

        temp = temp->lch;

    }

    node->book = temp->book;

    return temp;

}

Book *BST_Find(BST *bst, int num)

{

    Node *node = 0;

    node = BST_FindSeat(bst->root,num);

    if(node)

    {

        if(node->book->num == num)

        {

            return node->book;

        }

    }

    return 0;  

}

void BST_Inorder(Node *sr);

void BST_List(BST *bst)

{

    printf("보관 개수:%d\n",bst->count);

    BST_Inorder(bst->root);

}

void BST_Inorder(Node *sr)

{

    if(sr)

    {

        BST_Inorder(sr->lch);

        Book_View(sr->book);

        BST_Inorder(sr->rch);          

    }

}

 

//Program.c

#include "BinSearchTree.h"

int main()

{

    Book *book = 0;

    BST *bst = New_BST();

 

    BST_Insert(bst,New_Book("C언어","홍길동",10));

    BST_Insert(bst,New_Book("C++","홍길동",8));

    BST_Insert(bst,New_Book("자료구조","홍길동",7));

    BST_Insert(bst,New_Book("알고리즘","홍길동",12));

    BST_Insert(bst,New_Book("디자인패턴","홍길동",5));

    BST_Insert(bst,New_Book("소켓통신","홍길동",4));

   

    BST_List(bst);

    book = BST_Find(bst,5);

    if(book)

    {

        printf("검색 성공\n");

        Book_View(book);

    }

    else

    {

        printf("검색 실패\n");

    }

   

    BST_Remove(bst,5);

    BST_List(bst);

    Delete_BST(bst);

    return 0;

}