[디딤돌 자료구조와 알고리즘 with C] 3.4.2 이진 탐색 트리 코드

3.4.2 이진 탐색 트리 코드

이진탐색트리.zip

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

 

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

 

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

 

▷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;

}