Remoção de uma Arvore Binária de Busca(ABB)

#include <iostream>

using namespace std;

// Classe no
class no  {
   public:
      int chave;       
      no *pSubEsq;
      no *pSubDir;
   public:
      // Construtor
      no() : chave(0), pSubEsq(NULL),
             pSubDir(NULL) {}

      // Destruidor
      ~no() {}

}; // Fim: classe no.

// Classe ArvoreABB
class ArvoreABB  {
   public:
      no *pRaiz;             
   public:
      // Construtor
      ArvoreABB() : pRaiz(NULL) {
      }

	  ~ArvoreABB() {
		  destruir();
	  }

      bool vazia( void ) {
          return(pRaiz==NULL);
      }
	  
      void inserir(int valor)  {
         no *pnovo = new no;
         pnovo->chave = valor;
      if (pRaiz==NULL)
         pRaiz = pnovo;
      else {
         no *pAtual = pRaiz; 
         no *pPai;
         while(true) {
            pPai = pAtual;
            if (valor < pAtual->chave) {
               pAtual=pAtual->pSubEsq;
               if (pAtual == NULL) {
		          pPai->pSubEsq=pnovo;
                  return;
               }
            }else {
				if (valor > pAtual->chave) {
                   pAtual=pAtual->pSubDir;
                   if (pAtual == NULL) {
                      pPai->pSubDir=pnovo;
                      return;
				   }
				}else {
					cout << "\nElemento ja' existe!\n";
					return;
				}
			}  
		 }  
	  }

	  }


   void destruir() {
	   destruir_recursiva(pRaiz);
   }

   void destruir_recursiva(no *pRaiz) {

	   if (pRaiz != NULL) {
		   destruir_recursiva(pRaiz->pSubEsq);
		   destruir_recursiva(pRaiz->pSubDir);
		   delete pRaiz;

	   }
	   pRaiz = NULL;

   }

      void percursos(void) {
		  cout << "\nPre-ordem: ";
          preordem(pRaiz);
		  cout << "\nIn-ordem:  ";
          inordem(pRaiz);
		  cout << "\nPos-ordem: ";
          posordem(pRaiz);
		  cout << "\n\n";
      }

      void preordem(no *pRaiz) {
          if (pRaiz!=NULL) {
             cout << pRaiz->chave << " ";
			 preordem(pRaiz->pSubEsq);
             preordem(pRaiz->pSubDir);          
          }
      }

      void inordem(no *pRaiz) {
          if (pRaiz!=NULL) {
			 inordem(pRaiz->pSubEsq);
             cout << pRaiz->chave << " ";
             inordem(pRaiz->pSubDir);          
          }
      }

      void posordem(no *pRaiz) {
          if (pRaiz!=NULL) {
			 posordem(pRaiz->pSubEsq);
             posordem(pRaiz->pSubDir);          
             cout << pRaiz->chave << " ";
          }
      }

	  int quantidade(no *pRaiz) {
		  int N = 0, n1, n2;
		  if (pRaiz != NULL ) {
			  n1 = quantidade(pRaiz->pSubEsq);
			  n2 = quantidade(pRaiz->pSubDir);
			  N = n1 + n2 + 1;
		  }
	      return (N);
	  }

	  int altura(no *pRaiz) {
		  int h = -1, h1, h2;
		  if (pRaiz == NULL) 
			  return (-1);
		  else {
			  h1 = altura(pRaiz->pSubEsq);
			  h2 = altura(pRaiz->pSubDir);
			  h = (h1>h2) ? h1 : h2;
		  }
	      return (h+1);
	  }

	  void calcular() {
		  cout << "\nQuantidade de nos = " << quantidade(pRaiz) << endl;
		  cout << "\nAltura da Arvore = " << altura(pRaiz) << endl;
	  }

};  // Fim: classe ArvoreABB.



//	 Programa Principal
int main (void)
{
    ArvoreABB      Arvore;
    int             valor;
	char            opcao;

	
    do { 

		cout << "\n\tARVORES DE BUSCA BINARIA\n";
		cout << "\n\t1 - Inserir elementos";
		cout << "\n\t2 - Percursos na Arvore";
		cout << "\n\t3 - Quantidade de nos e Altura da Arvore";
		cout << "\n\t0 - Finalizar\n";
		cin >> opcao;

	switch (opcao) {
	case '1': cout << "\n\tEntre com o elemento a inserir: ";
		      cin >> valor;
		      Arvore.inserir( valor );
		      break;
	case '2': if ( !( Arvore.vazia() ) ) {
				  Arvore.percursos();
			  }else
				cout <<"\n\nArvore Vazia!\n";
			  break;
	case '3': Arvore.calcular();
			  break;
	case '0': cout << "\n\nT C H A U ! ! !\n";
		      break;
	default:  cout << "\n\nOpcao Invalida\n";
	};

	} while ( opcao != '0' );
	
	int resultado=0;
	return resultado;

}