이진 탐색 트리에서 erase, post-order traverse 구현하기 (Implement erase & post-order traverse on Binary Search Tree)
Source Code
BST.h
cpp
class Node
{
public:
Node* left;
Node* right;
int value;
};
class BST
{
private:
Node* ghost;
Node* GetRoot();
public:
BST();
~BST();
void insert(int k);
Node* erase(int k);
void free(Node* pNode);
Node* search(int k);
void travel(Node* pNode);
void ShowAll();
void post_travel(Node* pNode);
};
BST.cpp
cpp
#include "BST.h"
BST::BST()
{
ghost = new Node;
ghost->left=NULL;
ghost->right=NULL;
ghost->value=214783647;
}
BST::~BST()
{
free(ghost);
}
Node* BST::GetRoot()
{
return ghost->left;
}
void BST::insert(int k)
{
Node* t = ghost;
Node* p = t->left;
while( p )
{
if( p->value > k )
{
t = p;
p = p->left;
}
else
{
t = p;
p = p->right;
}
}
p = new Node;
p->left=NULL;
p->right=NULL;
p->value=k;
if( t->value > k )
t->left = p;
else
t->right = p;
}
void BST::travel(Node* pNode)
{
if( pNode )
{
travel(pNode->left);
std::cout<<pNode->value<<endl;
travel(pNode->right);
}
}
void BST::ShowAll()
{
//travel(GetRoot());
post_travel(GetRoot());
}
void BST::free(Node* pNode)
{
if( pNode )
{
free( pNode->left );
free( pNode->right);
delete pNode;
}
}
Node* BST::search( int k )
{
Node* p=GetRoot();
while( p )
{
if( p->value == k )
return p;
else if( p->value > k )
p = p->left;
else
p = p->right;
}
return p;
}
Node* BST::erase(int k)
{
// find k
Node* p = search(k);
Node* temp;
// do nothing if k is not found
if(!p) return NULL;
// remove it from the tree
// leaf element
if(!p->right||!p->left)
{
// find p's parent node
p=GetRoot();
while(p)
{
// p is left subtree
if(p->left&&p->left->value == k)
{
temp = p->left;
if(temp->left)
{
p->left = temp->left;
}
else
{
p->left = temp->right;
}
break;
}
// p is right subtree
else if(p->right&&p->right->value == k)
{
temp = p->right;
if(temp->left)
{
p->right = temp->left;
}
else
{
p->right = temp->right;
}
break;
}
else if( p->value > k )
{
p = p->left;
}
else
{
p = p->right;
}
}
// return the found node
return temp;
}
// degree 2 node
else
{
int t;
temp = p;
// 왼쪽에서 값을 가져오는 것으로 함
p = p->left;
// 왼쪽에서 가장 큰 수-> 가장 오른쪽에 있는 수
while( p->right )
{
p = p->right;
}
t = p->value;
//recursive algorithm
delete( erase(p->value) );
temp->value = t;
// return NULL pointer
return NULL;
}
}
void BST::post_travel(Node* pNode)
{
if( pNode )
{
post_travel(pNode->left);
post_travel(pNode->right);
std::cout<<pNode->value<<endl;
}
}