7.3 이진 탐색 트리 설계 및 사용

이번에는 이진 탐색 트리 설계 및 이를 사용하는 프로그램을 작성합시다. 여기에서 구현할 이진 탐색 트리는 도서 개체를 보관하고 삭제, 검색, 전체 보기를 할 수 있는 기능을 제공하기로 해요.

STL에서 제공하는 map 사용하는 방법을 익히고 난 후에 다시 한 번 STL의 map을 모델로 자신의 map을 구현할 것입니다. 여기에서는 이진 탐색 트리 개념을 잡기 위해 비교적 간단하게 구현해 보아요.

프로젝트를 생성한 후에 공통으로 사용할 파일(3.1.1 참고)을 추가하세요. 그리고 여기에서 보관할 도서를 Book 클래스로 정의합시다.

class Book
{
    //도서는 상수화 멤버로 도서 번호와 도서명을 멤버 필드로 추가하세요.
    const int bnum;
    string title;
public:
    //생성자에서 도서 번호와 도서명을 입력 인자로 받기로 해요.
    Book(int bnum,string title);
    //도서 번호와 도서명에 관한 접근자와 정보를 출력하는 메서드를 제공하세요.
    int GetBNum()const;
    string GetTitle()const;
    void View()const;
};

구현도 간단하겠죠. 별다른 설명은 필요없을 것이라 생각합니다.

#include "Book.h"
Book::Book(int bnum,string title):bnum(bnum)
{
    this->title = title;
}
int Book::GetBNum()const
{
    return bnum;
}
string Book::GetTitle()const
{
    return title;
}
void Book::View()const
{
    cout<<bnum<<", "<<title<<endl;
}

여기서 구현할 이진 탐색 트리는 도서를 보관할 것입니다. 먼저 이진 탐색 트리의 노드를 정의하기로 해요.

struct Node
{
    //멤버 필드로 도서 개체를 기억하는 멤버 필드가 필요하겠죠.
    Book *book;
    //왼쪽 자식과 오른쪽 자식을 기억하는 멤버가 필요합니다.
    Node *left;
    Node *right;
    //삭제를 편하게 하기 위해 부모를 기억하는 멤버도 추가하세요.
    Node *parent;
    //생성자에는 도서 개체를 입력 인자로 받아 멤버 필드를 설정하게 구현하세요.
    Node(Book *book)
    {
        this->book = book;
        left = right = parent = 0;
    }
};

이진 탐색 트리는 BinSearchTree 이름의 클래스로 정의합시다.

class BinSearchTree
{
    //최상위 노드를 기억할 root 멤버 필드가 필요하겠죠.
    Node *root;
public:
    BinSearchTree(void);
    ~BinSearchTree(void);
    //도서를 추가하는 메서드를 제공합시다. 
    //여기에서는 추가할 도서의 정보를 입력 인자로 받아 
    //같은 도서 번호를 갖는 개체가 없을 때만 생성해서 보관하기로 해요. 
    //그리고 생성 여부를 반환하기로 합시다.
    bool AddBook(int bnum,string title);
    //도서 번호로 검색하는 기능도 제공합시다. 
    //간단히 구현하기 위해 내부에서 검색한 도서 정보를 출력하고 
    //호출한 곳에는 검색 성공 여부만 반환하기로 해요.
    bool FindBook(int bnum)const;
    //도서 번호로 삭제하는 기능도 제공합시다. 
    //호출하는 곳에 삭제 여부를 반환하게 구현합시다.
    bool RemoveBook(int bnum);
    //전체 도서 정보를 출력하는 기능도 제공합시다.
    void ListAll()const;    
};

구체적인 구현은 나머지 부분을 구현한 후에 하기로 해요.

#include "BinSearchTree.h"
BinSearchTree::BinSearchTree(void)
{
일단 멤버 root는 0으로 초기화하세요.
    root = 0;
}
BinSearchTree::~BinSearchTree(void)
{ 
}
bool BinSearchTree::AddBook(int bnum,string title)
{
    return false;
}
bool BinSearchTree::FindBook(int bnum)const
{
    return false;
}
bool BinSearchTree::RemoveBook(int bnum)
{
    return false;
}
void BinSearchTree::ListAll()const
{
}

도서 관리 프로그램을 표현할 App 클래스를 추가하여 구현합시다.

class App
{
    //멤버 필드로 도서를 보관할 이진 탐색 트리를 추가하세요.
    BinSearchTree bstree;
public:    
    void Run();
private:
    //내부 기능으로 메뉴와 도서 추가, 도서 삭제, 도서 검색, 전체 보기를 제공합시다.
    int SelectMenu();
    void AddBook(); //도서 추가
    void RemoveBook();//도서 삭제
    void FindBook()const; //도서 검색    
    void ListAll()const; //전체 보기
};

이제 App의 각 기능을 구현합시다.

void App::Run()
{
    //메뉴를 선택하여 선택한 기능을 반복하는 반복문을 구현하세요. 
    int key=NO_DEFINED;
    while((key = SelectMenu())!=ESC)
    {
        //선택한 기능에 따라 제공할 기능을 호출하게 구현하세요.
        switch(key)
        {
        case F1: AddBook(); break;
        case F2: RemoveBook(); break;
        case F3: FindBook(); break;
        case F4: ListAll(); break;        
        default: cout<<"잘못 선택하셨습니다."<<endl; break;
        }
        cout<<"아무 키나 누르세요."<<endl;
        ehglobal::getkey();
    }
}
int App::SelectMenu()
{
    //콘솔 화면을 지운 후에 메뉴를 출력하세요.
    ehglobal::clrscr();//콘솔 화면을 지우기
    cout<<"도서 관리 프로그램 [ESC]: 종료"<<endl;
    cout<<"F1: 도서 추가 F2: 도서 삭제 F3: 도서 검색 F4: 전체 보기"<<endl;
    //사용자가 입력한 기능 키를 반환하세요.
    return ehglobal::getkey();//사용자가 입력한 기능 키 반환
}
void App::AddBook() //도서 추가
{
    //도서 추가에서는 먼저 주요 키(Primary Key)인 도서 번호를 입력받으세요.
    cout<<"추가할 도서 번호:";
    int num = ehglobal::getnum();
    //입력한 도서 번호로 검색하여 이미 존재하는지 확인하세요.
    if(bstree.FindBook(num))
    {
        cout<<"이미 존재합니다."<<endl;
        return;
    }
    //도서명을 입력받습니다.
    cout<<"도서명:";
    string title = ehglobal::getstr();
    //입력한 정보를 입력 인자로 전달하여 도서를 추가하세요.
    bstree.AddBook(num,title);
}
void App::RemoveBook()//도서 삭제
{
    //삭제할 도서 번호를 입력받습니다.
    cout<<"삭제할 도서 번호:";
    int num = ehglobal::getnum();
    //이진 탐색 트리에게 도서를 삭제 요청합니다. 그리고 성공 여부를 출력하세요.
    if(bstree.RemoveBook(num))
    {
        cout<<"삭제하였습니다."<<endl;        
    }
    else
    {
        cout<<"존재하지 않는 도서입니다."<<endl;
    }
}
void App::FindBook()const //도서 검색    
{
    //검색할 도서 번호를 입력받습니다.
    cout<<"검색할 도서 번호:";
    int num = ehglobal::getnum();
    //도서 검색을 요청하세요. 
    //이진 탐색 트리의 검색 기능에서 검색 후에 출력까지 하기로 했어요.
    if(bstree.FindBook(num)==0)
    {
        //만약 검색 실패했을 때는 메시지를 출력하세요.
        cout<<"존재하지 않는 도서입니다."<<endl;
    }
}
void App::ListAll()const //전체 보기
{
    //이진 탐색 트리의 전체 보기 기능을 호출하세요.
    bstree.ListAll();
}

진입점 main에서는 App 개체를 생성하고 가동 후에 소멸하세요.

int main()
{
    App *app = new App();
    app->Run();
    delete app;
    return 0;
}

다음은 이제까지 작성한 코드입니다.

//Book.h
#pragma once
#include "ehglobal.h"
class Book
{    
    const int bnum;
    string title;
public:
    Book(int bnum,string title);    
    int GetBNum()const;
    string GetTitle()const;
    void View()const;
};

//Book.cpp
#include "Book.h"

Book::Book(int bnum,string title):bnum(bnum)
{
    this->title = title;
}
int Book::GetBNum()const
{
    return bnum;
}
string Book::GetTitle()const
{
    return title;
}
void Book::View()const
{
    cout<<bnum<<", "<<title<<endl;
}

//BinSearchTree.h
#pragma once
#include "Book.h"
struct Node
{
    Book *book;
    Node *left;
    Node *right;
    Node *parent;
    Node(Book *book)
    {
        this->book = book;
        left = right = parent = 0;
    }    
};    

class BinSearchTree
{    
    Node *root;
public:
    BinSearchTree(void);
    ~BinSearchTree(void);
    bool AddBook(int bnum,string title);
    bool FindBook(int bnum)const;
    bool RemoveBook(int bnum);
    void ListAll()const;    
private:
    Node *Find(Node *sr, int bnum)const;
    void HangNode(Node *parent, Node *now);
    void DeHang(Node *now);
    void PreOrder(Node *sr)const;    
    void InOrder(Node *sr)const;    
    void PostOrder(Node *sr)const;
    void Clear(Node *sr);
};

//BinSearchTree.cpp
#include "BinSearchTree.h"
BinSearchTree::BinSearchTree(void)
{
    root = 0;
}
BinSearchTree::~BinSearchTree(void)
{ 
}
bool BinSearchTree::AddBook(int bnum,string title)
{
    return false;
}
bool BinSearchTree::FindBook(int bnum)const
{
    return false;
}
bool BinSearchTree::RemoveBook(int bnum)
{
    return false;
}
void BinSearchTree::ListAll()const
{
}

//App.h
#pragma once
#include "ehglobal.h"
#include "BinSearchTree.h"
class App
{
    BinSearchTree bstree;
public:    
    void Run();
private:
    int SelectMenu();
    void AddBook(); //도서 추가
    void RemoveBook();//도서 삭제
    void FindBook()const; //도서 검색    
    void ListAll()const; //전체 보기
};

//App.cpp
#include "App.h"

void App::Run()
{
    int key=NO_DEFINED;
    while((key = SelectMenu())!=ESC)
    {
        switch(key)
        {
        case F1: AddBook(); break;
        case F2: RemoveBook(); break;
        case F3: FindBook(); break;
        case F4: ListAll(); break;        
        default: cout<<"잘못 선택하셨습니다."<<endl; break;
        }
        cout<<"아무 키나 누르세요."<<endl;
        ehglobal::getkey();
    }
}

int App::SelectMenu()
{
    ehglobal::clrscr();//콘솔 화면을 지우기
    cout<<"도서 관리 프로그램 [ESC]: 종료"<<endl;
    cout<<"F1: 도서 추가 F2: 도서 삭제 F3: 도서 검색 F4: 전체 보기"<<endl;

    return ehglobal::getkey();//사용자가 입력한 기능 키 반환
}
void App::AddBook() //도서 추가
{
    cout<<"추가할 도서 번호:";
    int num = ehglobal::getnum();
    if(bstree.FindBook(num))
    {
        cout<<"이미 존재합니다."<<endl;
        return;
    }
    cout<<"도서명:";
    string title = ehglobal::getstr();
    bstree.AddBook(num,title);
}

void App::RemoveBook()//도서 삭제
{
    cout<<"삭제할 도서 번호:";
    int num = ehglobal::getnum();
    
    if(bstree.RemoveBook(num))
    {
        cout<<"삭제하였습니다."<<endl;        
    }
    else
    {
        cout<<"존재하지 않는 도서입니다."<<endl;
    }
}

void App::FindBook()const //도서 검색    
{
    cout<<"검색할 도서 번호:";
    int num = ehglobal::getnum();
    
    if(bstree.FindBook(num)==0)    
    {
        cout<<"존재하지 않는 도서입니다."<<endl;
    }
}

void App::ListAll()const //전체 보기
{
    bstree.ListAll();
}

//Program.cpp
#include "App.h"
int main()
{
    App *app = new App();
    app->Run();
    delete app;
    return 0;
}