이진 탐색 트리에서 erase, post-order traverse 구현하기 (Implement erase & post-order traverse on Binary Search Tree)

BST.h

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

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