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


/*****

Faça função 

int ehDescendente (no *x, no *y); 

que devolve 1 se x é descendente de y ou 0 caso contrário

******/

int ehDescendente (no *x, no *y){
  if (x == NULL || y == NULL) return 0;
  if (x == y) return 1;
  return (ehDescendente (x, y->esq) || ehDescendente (x, y->dir));
} 

int ehDescendente (no *x, no *y){
  if (x == NULL || y == NULL) return 0;
  if (x == y) return 1; 
  return (ehDescendente (x->pai, y));
}


/******

Percurso em profundidade 

void profundidade (no *raiz);

Imprime os nós da árvore em profundidade

******/

void profundidade (no *raiz){
  if (raiz != NULL){
    printf("%d ", raiz->info);
    profundidade (raiz->esq);
    profundidade (raiz->dir);
  }
} 

/******

Percurso em largura 

void largura (no *raiz); 

Imprime os nós da árvore em largura

*******/

void largura (no *raiz){
  Fila * f = criaFila (10);
  no *p; 
  if (raiz != NULL){
    f = insereFila (f, raiz);
    while (!filaVazia(f)){
      p = removeFila(f);
      printf("%d ", p->info);
      if (p->esq != NULL)
	f = insereFila (f, p->esq);
      if (p->dir != NULL)
	f = insereFila (f, p->dir);
    }
  }
}






/******

Percurso in-ordem: esquerda, raiz, direita

void inordem (no *raiz); 


********/

void inordem (no *raiz) {
  if (raiz != NULL){
    inordem (raiz->esq);
    printf("%d ", raiz->info);
    inordem (raiz->dir);
  }
}


/******

Percurso pre-ordem: raiz, esquerda, direita

void preordem (no *raiz); 


********/

void preordem (no *raiz) {
  if (raiz != NULL){
    printf("%d ", raiz->info);
    preordem (raiz->esq);
    preordem (raiz->dir);
  }
}

/******

Percurso pos-ordem: esquerda, direita, raiz

void posordem (no *raiz); 


********/

void posordem (no *raiz) {
  if (raiz != NULL){
    posordem (raiz->esq);
    posordem (raiz->dir);
    printf("%d ", raiz->info);
  }
}




/*******

Lista as folhas descendentes de um nó x

void folhasDescendentes (no *x); 

*******/

void folhasDescendentes (no *x){
  if (x != NULL){
    if (x->esq == NULL && x->dir == NULL){
      printf("%d ", x->info);
      return;
    }
    folhasDescendentes (x->esq);
    folhasDescendentes (x->dir);
  }
}


/************

Devolve o ancestral comum mais próximo de dois nós

no * ancComumMaisProximo (no *x, no *y); 

*************/

no * ancComumMaisProximo (no *x, no *y){
  if (x == NULL || y == NULL)
    return NULL;
  if (ehDescendente (x, y))
    return y;
  if (ehDescendente (y, x))
    return x;
  return (ancComumMaisProximo (x->pai, y));
}