이제 앞에서 설계한 이진 탐색 트리를 구체적으로 구현합시다.
먼저 이진 탐색 트리의 추가 기능인 AddBook 메서드를 구현하기로 해요.
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
{
//만약 검색할 서브 트리의 루트가 0인지 확인하세요.
if(sr==0)
{
//서브 트리의 루트가 0이라는 말은 root가 0이라는 말과 같습니다.
//이 메서드에서는 재귀 호출을 사용할 것이며 언제나 서브 트리가 존재할 때만 호출할 것입니다.
//따라서 처음 호출할 때 sr이 0일 때만 이 조건에 해당하며 결국 root가 0이라는 말과 같습니다.
return sr;
}
//입력 받은 도서 번호와 서브 트리의 루트에 보관한 도서의 번호의 차이를 계산합니다.
int gap = bnum - sr->book->GetBNum();
if(gap==0)
{
//만약 차이가 없다면 sr을 반환하세요.
return sr;
}
if(gap>0)
{
//차이가 0보다 크면 오른쪽 서브 트리에서 탐색해야 합니다.
if(sr->right)
{
//만약 오른쪽 서브 트리가 있으면 재귀 호출하여 탐색한 값을 by pass 하세요.
return Find(sr->right,bnum);
}
//만약 오른쪽 서브 트리가 없으면 탐색을 끝내고 현재 sr을 반환하세요.
return sr;
}
//gap이 0이거나 0보다 크면 반환했죠. 여기에 도달했다는 것은 gap이 0보다 작다는 것입니다.
if(sr->left)
{
//왼쪽 서브 트리가 있으면 재귀 호출하여 탐색한 값을 by pass 하세요.
return Find(sr->left,bnum);
}
//만약 왼쪽 서브 트리가 없으면 탐색을 끝내고 현재 sr을 반환하세요.
return sr;
}
이제 추가할 노드와 부모 노드의 연결하는 메서드를 구현합시다.
void BinSearchTree::HangNode(Node *parent, Node *now)
{
if(parent == 0)
{
//만약 부모가 없으며 새로운 노드가 첫 노드이므로 root로 설정하세요.
root = now;
return;
}
//먼저 새로운 노드의 parent 링크를 설정하세요.
now->parent = parent;
//그리고 부모 노드의 어느 쪽에 매달 것인지 판단하기 위해 키 값의 차이를 계산하세요.
int gap = now->book->GetBNum() - parent->book->GetBNum();
//차이가 0보다 크면 부모의 오른쪽 자식으로 매달고 그렇지 않으면 왼쪽 자식으로 매다세요.
if(gap>0)
{
parent->right = now;
}
else
{
parent->left = now;
}
}
이제 사용하는 곳에서 검색에 사용할 FindBook 메서드를 구현합시다.
bool BinSearchTree::FindBook(int bnum)const
{
//먼저 bnum으로 검색합니다.
Node *now = Find(root,bnum);
if(now)
{
//now가 존재하면 now에 보관한 도서 개체를 구하세요.
Book *sbook = now->book;
if(sbook->GetBNum() == bnum)
{
//만약 도서 개체의 도서 번호와 입력받은 bnum이 같으면 검색 성공입니다.
//여기에서는 도서 정보를 출력하게로 했죠.
sbook->View();
return true;
}
}
//여기에 도달했다는 것은 검색 실패를 의미합니다.
return false;
}
도서 삭제 기능을 구현합시다.
bool BinSearchTree::RemoveBook(int bnum)
{
//먼저 bnum으로 노드를 검색하세요.
Node *now = Find(root,bnum);
if(now)
{
//now가 존재하면 now에 보관한 도서 개체를 구하세요.
Book *sbook = now->book;
if(sbook->GetBNum() == bnum)
{
//만약 도서 개체의 도서 번호와 입력받은 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;
}
//now에 보관한 도서 개체와 대체할 노드에 보관한 도서 개체를 교환하세요.
Book *tmpbook = now->book;
now->book = alter->book;
alter->book = tmpbook;
//이제 대체할 노드를 now에 설정하세요.
//언제나 now는 자식이 없거나 하나만 있는 노드라는 논리가 성립합니다.
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
{
//부모가 없다는 것은 now가 root라는 것입니다.
//따라서 now를 삭제하면 자식 노드를 root로 설정하세요.
root = child;
}
if(child)
{
//자식이 있다면 자식의 부모 링크를 pa로 설정하세요.
child->parent = pa;
}
//삭제할 now의 도서 개체를 소멸하고 now 노드도 소멸하세요.
delete now->book;
delete now;
}
전체 출력하는 ListAll 메서드를 구현합시다.
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이 참일 때만 수행합니다.
//따라서 sr이 0일 때가 재귀의 탈출 조건입니다.
//먼저 서브 트리의 루트 정보를 출력합니다.
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;
}
}