[C언어 알고리즘] 3.4.4 이진 탐색 트리 소스 코드
테스트 로직을 구현합시다.
테스트 로직은 단순히 이진 탐색 트리를 생성한 후에 다양한 도서 정보를 추가하고 검색과 삭제 기능 등을 호출하여 잘 동작하는지 확인하는 것입니다.
이 부분에 관한 별도의 설명은 생략할게요.
//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;
}
'언어 자료구조 알고리즘 > 디딤돌 알고리즘 (C언어)' 카테고리의 다른 글
| [C언어 알고리즘] 3.5.4 힙 정렬 알고리즘 소스 코드 (0) | 2016.11.30 |
|---|---|
| [C언어 알고리즘] 3.5.3 힙 정렬 알고리즘 구현 (0) | 2016.11.30 |
| [C언어 알고리즘] 3.5.2 힙 정렬 알고리즘 성능 분석 (0) | 2016.11.30 |
| [C언어 알고리즘] 3.5.1 힙 정렬 알고리즘 소개 (0) | 2016.11.30 |
| [C언어 알고리즘] 3.5 힙 정렬(Heap Sort) 알고리즘 (0) | 2016.11.30 |
| [C언어 알고리즘] 3.4.3 이진 탐색 트리 구현 (0) | 2016.11.30 |
| [C언어 알고리즘] 3.4.2 이진 탐색 트리(Binary Search Tree) (0) | 2016.11.30 |
| [C언어 알고리즘] 3.4.1 트리의 용어 (0) | 2016.11.30 |
| [C언어 알고리즘] 3.4 이진 탐색 트리 (0) | 2016.11.30 |
| [C언어 알고리즘] 3.3.3 퀵 정렬 알고리즘 소스 코드 (0) | 2016.11.30 |