[알고리즘 C언어] 3.4.4 이진 탐색 트리 소스 코드

다음은 C언어로 작성한 이진 탐색 트리 소스 코드와 이를 이용하여 도서 정보 추가, 검색, 삭제 기능 등을 호출하여 잘 동작하는지 확인하는 소스 코드입니다.

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