/* Árvores de Busca Binária */


typedef struct cel {
  int info;
  struct cel * esq;
  struct cel * dir;
} no;

/* Busca um elemento na árvore de busca binária

no * busca (no * raiz, int x); 

*/

no * busca (no * raiz, int x){
  if (raiz == NULL || raiz->info == x)
    return raiz;
  if (x < raiz->info)
    return busca (raiz->esq, x);
  return busca (raiz->dir, x);
}

no * busca (no * raiz, int x){
  no * p = raiz;
  while (p != NULL && p->info != x)
    if (x < p->info)
      p = p->esq;
    else
      p = p->dir;
  return p;
}
      

/* Devolve o máximo de uma ABB

no * maximo (no * raiz); 

*/

no * maximo (no * raiz){
  no * p = raiz;
  while (p != NULL && p->dir != NULL)
    p = p->dir;
  return p;
} 

no * maximo (no * raiz){
  if (raiz == NULL || raiz->dir == NULL)
    return raiz;
  return maximo(raiz->dir);
} 

/* Insere um elemento em uma ABB, devolve a raiz da árvore 
   com o elemento inserido

no * insere (no * raiz, int x); 

*/ 

no * insere (no * raiz, int x){
  if (raiz == NULL){
    raiz = malloc (sizeof(no));
    raiz->info = x;
    raiz->dir = raiz->esq = NULL;
    return raiz;
  }
  if (x < raiz->info)
    raiz->esq = insere (raiz->esq, x);
  else if (x > raiz->info)
    raiz->dir = insere (raiz->dir, x);
  return raiz;
}

no * insere (no * raiz, int x){
  no *p, *ant, *novo = malloc(sizeof(no));
  novo->info = x;
  novo->esq = novo->dir = NULL;
  p = raiz;
  ant = NULL; 
  while (p != NULL && p->info != x){
    ant = p; 
    if (x < p->info)
      p = p->esq;
    else 
      p = p->dir;
  }
  if (p == NULL){
    if (ant == NULL) /* árvore estava vazia */
      return novo;
    if (x < ant->info)
      ant->esq = novo;
    else
      ant->dir = novo;
  }
  return raiz;
}