7.4 이진 탐색 트리 구현 [소스 코드]

다음은 이진 탐색 트리를 구현한 내용입니다.

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

bool BinSearchTree::AddBook(int bnum,string title)
{
    Node *parent = Find(root,bnum);
    if(parent)
    {
        Book *sbook = parent->book;
        if(sbook->GetBNum() == bnum)
        {
            return false;
        }
    }
    Book *book = new Book(bnum,title);
    HangNode(parent,new Node(book));
    return true;
}

Node *BinSearchTree::Find(Node *sr, int bnum)const
{
    if(sr==0)
    {
        return sr;
    }
    int gap = bnum - sr->book->GetBNum();
    if(gap==0)
    {
        return sr;
    }
    if(gap>0)
    {
        if(sr->right)
        {
            return Find(sr->right,bnum);
        }
        return sr;
    }
    if(sr->left)
    {
        return Find(sr->left,bnum);
    }
    return sr;
}

void BinSearchTree::HangNode(Node *parent, Node *now)
{
    if(parent == 0)
    {
        root = now;
        return;
    }

    now->parent = parent;
    int gap = now->book->GetBNum() - parent->book->GetBNum();
    if(gap>0)
    {
        parent->right = now;
    }
    else
    {
        parent->left = now;
    }
}

bool BinSearchTree::FindBook(int bnum)const
{
    Node *now = Find(root,bnum);

    if(now)
    {
        Book *sbook = now->book;
        if(sbook->GetBNum() == bnum)
        {
            sbook->View();
            return true;
        }
    }    
    return false;
}

bool BinSearchTree::RemoveBook(int bnum)
{
    Node *now = Find(root,bnum);
    if(now)
    {
        Book *sbook = now->book;
        if(sbook->GetBNum() == bnum)
        {            
            DeHang(now);
            return true;
        }
    }    
    return false;
}
void BinSearchTree::DeHang(Node *now)
{
    if(now->left && now->right)
    {
        Node *alter = now->left;
        while(alter->right)
        {
            alter = alter->right;
        }
        Book *tmpbook = now->book;
        now->book = alter->book;
        alter->book = tmpbook;
        now = alter;
    }

    Node *pa = now->parent;
    Node *child = 0;
    (child = now->left)||(child = now->right);
    if(pa)
    {
        if(pa->left == now)
        {
            pa->left = child;
        }
        else
        {
            pa->right = child;
        }
    }
    else
    {
        root = child;
    }
    if(child)
    {
        child->parent = pa;
    }
    delete now->book;
    delete now;
}

void BinSearchTree::ListAll()const
{    
    cout<<"=== Pre order ===="<<endl;
    PreOrder(root);    
    cout<<"===  In order ===="<<endl;
    InOrder(root);    
    cout<<"=== Post order ===="<<endl;
    PostOrder(root);
}

void BinSearchTree::PreOrder(Node *sr)const
{
    if(sr)
    {
        sr->book->View();
        PreOrder(sr->left);
        PreOrder(sr->right);
    }
}

void BinSearchTree::InOrder(Node *sr)const
{
    if(sr)
    {        
        InOrder(sr->left);
        sr->book->View();
        InOrder(sr->right);
    }
}


void BinSearchTree::PostOrder(Node *sr)const
{
    if(sr)
    {        
        PostOrder(sr->left);
        PostOrder(sr->right);
        sr->book->View();
    }
}

BinSearchTree::~BinSearchTree(void)
{
    Clear(root);
}

void BinSearchTree::Clear(Node *sr)
{
    if(sr)
    {        
        Clear(sr->left);
        Clear(sr->right);
        delete sr->book;
        delete sr;
    }
}