public class ArvoreBB
{
  No Raiz;
  
  public ArvoreBB()
    {
      Raiz = null;
    }
  public ArvoreBB(No no)
    {
      Raiz = no;
    }
  public boolean Busca( int x )
    {
      if (Raiz == null) return false;
      if (Raiz.leInfo() == x) return true;
      if (Raiz.leInfo() < x) 
	return Raiz.leEsq().Busca(x);
      return Raiz.leDir().Busca(x);
    }
  public void Insere(int x)
    {
      if( Raiz == null ) {
	No novo = new No();
	novo.mudaInfo(x);
	novo.mudaEsq(null);
	novo.mudaDir(null);
	Raiz = novo;
      }
      else if (x < Raiz.leInfo()){
	  if (Raiz.leEsq() != null){
	    Raiz.leEsq().Insere(x);
	}
	else{
	  No novo = new No();
	  novo.mudaInfo(x);
	  novo.mudaEsq(null);
	  novo.mudaDir(null);
	  Raiz.mudaEsq(new ArvoreBB(novo));
	}
	  
      }
      else if (x > Raiz.leInfo()){
	if (Raiz.leDir() != null){
	  Raiz.leDir().Insere(x);  
	}
	else{
	  No novo = new No();
	  novo.mudaInfo(x);
	  novo.mudaEsq(null);
	  novo.mudaDir(null);
	  Raiz.mudaDir(new ArvoreBB(novo));
	}	
      }
    }
  public void Remove( int x)
    {
      if( Raiz != null){
	
	if (Raiz.leInfo() > x) {
	  if (Raiz.leEsq() != null){
	    if (Raiz.leEsq().Raiz.leInfo() == x){
	      // achou x!
	      
	      No q = Raiz.leEsq().Raiz;
	      if (q.leDir() == null) 
		Raiz.mudaEsq(q.leEsq());
	      else if (q.leEsq() == null)
		Raiz.mudaEsq(q.leDir());
	      else{
		// q tem dois filhos!! Vamos substituir pelo maior menor
		No ant = q;
		No p   = q.leEsq().Raiz;
		while (p.leDir() != null){
		  ant = p;
		  p = p.leDir().Raiz;
		}
		q.mudaInfo(p.leInfo());
		if (ant == q) 
		  ant.mudaEsq(p.leEsq());
		else
		  ant.mudaDir(p.leEsq());
	      }
	    }
	    else Raiz.leEsq().Remove(x);
	    
	  }
	}
	else if (Raiz.leInfo() < x) {
	  if (Raiz.leDir() != null){
	    if (Raiz.leDir().Raiz.leInfo() == x){
	      // achou x!
	      No q = Raiz.leDir().Raiz;
	      if (q.leDir() == null) 
		Raiz.mudaDir(q.leEsq());
	      else if (q.leEsq() == null)
		Raiz.mudaDir(q.leDir());
	      else{
		// q tem dois filhos!! Vamos substituir pelo maior menor
		No ant = q;
		No p   = q.leEsq().Raiz;
		while (p.leDir() != null){
		  ant = p;
		  p = p.leDir().Raiz;
		}
		q.mudaInfo(p.leInfo());
		if (ant == q) 
		  ant.mudaEsq(p.leEsq());
		else
		  ant.mudaDir(p.leEsq());
	      }
	    }
	    else Raiz.leDir().Remove(x);
	    
	  }
	}	  
	else {
	  // x esta' na raiz!!
	      if (Raiz.leDir() == null) 
		if (Raiz.leEsq() != null ) 
		  Raiz = Raiz.leEsq().Raiz;
	        else
		  Raiz = null;
	      else if (Raiz.leEsq() == null)
		Raiz = Raiz.leDir().Raiz;
	      else{
		// Raiz tem dois filhos!! Vamos substituir pelo maior menor
		No ant = Raiz;
		No p   = Raiz.leEsq().Raiz;
		while (p.leDir() != null){
		  ant = p;
		  p = p.leDir().Raiz;
		}
		Raiz.mudaInfo(p.leInfo());
		if (ant == Raiz) 
		  Raiz.mudaEsq(p.leEsq());
		else
		  ant.mudaDir(p.leEsq());
	      }
	}
      }
    }

  public void ImprimePreOrdem()
    {
      if(Raiz != null){
	System.out.print(Raiz.leInfo());
	if(Raiz.leEsq() != null) Raiz.leEsq().ImprimePreOrdem();
	if(Raiz.leDir() != null) Raiz.leDir().ImprimePreOrdem();
      }
    } 
  public void ImprimeInOrdem()
    {
      if(Raiz != null){
	if(Raiz.leEsq() != null) Raiz.leEsq().ImprimeInOrdem();
	System.out.print(Raiz.leInfo());
	if(Raiz.leDir() != null) Raiz.leDir().ImprimeInOrdem();
      }
    }   
}