/* Algumas respostas adicionais de exercicios da Lista 3 
   cortesia do prof. Angelo Ciarlini 
*/

#include <stdlib.h>
#include "arv1.h"

/*  EX. 4  */

int maior(int x, int y)
{ 
  if (x>y) return x;
  return y;
}


int altura(ARV a)

{
  if (a==NULL) return 0;
  if ((a->dir==NULL) && (a->esq==NULL)) return 0;
  return maior(altura(a->esq),altura(a->dir))+1;
}
	

/*  EX. 6  */

PT acha_no(ARV a,ARV pai_de_a, int v,ARV *pai_de_res)
/*
   procura um nó com um certo valor,
   "pai_de_a" é o pai da árvore que
   está sendo pesquisada.

  *pai_de_res conterá, ao final, o endereço
  do pai do nó encontrado.


  se o valor não ocorre, retorna NULL

*/

{
   if (a==NULL) return NULL;
   if (a->val==v)
      {	
         *pai_de_res=pai_de_a;
	 return a;
      }
   if (a->val>v) return acha_no(a->esq,a,v,pai_de_res);
   else return acha_no(a->dir,a,v,pai_de_res);
}



void remove_val(ARV *a, int v)	
{
   PT p, r, pai;
   PT *posicao;  /* endereco onde sera colocado
  	            o substituto do no a remover
  	          */

   p=acha_no(*a,NULL,v,&pai);

/* se valor não está na árvore não há nada a fazer */
   if (p==NULL) return; 

/* localizar o endereço do ponteiro para o substituto */
   if (pai==NULL)
      posicao=a;  /* o nó é a raiz  */
   else 
      if (p==pai->esq)  /* o nó está à esq. do pai */
         posicao=&(pai->esq); /* o nó está à dir. do pai */
      else 
	 posicao=&(pai->dir);

   if (p->esq==NULL)  /* se não há nó à esq., o substituto
		         é o que está à direita */
      *posicao=p->dir;
   else
   {
		/* para colocar o nó à esquerda como substituto,
		   é preciso achar posição onde subárvore da
		   direita deve ser inserida
		*/
     *posicao=p->esq;
     if (p->dir!=NULL)
	{
	   for (r=p->esq;r->dir!=NULL;r=r->dir);
  	   r->dir=p->dir;
	}
   }

   free(p);
}	



/* EX. 8  */


/* 8.a  */

ARV copia_arv(ARV a)
{
   ARV a1;

   if (a==NULL) return NULL;
   a1= (ARV) malloc(sizeof(NO));
   a1->dir=copia_arv(a->dir);
   a1->val=a->val;
   a1->esq=copia_arv(a->esq);
   return a1;
}

/* solução idêntica para arvore qualquer:
Basta trocar a a->esq por a->prim e a->dir por a->prox */

/* 8.b  */

int soma(ARV a)
{
   if (a==NULL) return 0;
   return soma(a->esq)+soma(a->dir)+a->val;
}

/* 8.c  */

int max_arv(ARV a)
/* Retorna o valor máximo de uma árvore 
   binária que não é vazia */
{
   int v,v_esq,v_dir;

   if ((a->esq==NULL) && (a->dir==NULL))
      return a->val;

   if (a->dir==NULL)
      v=max_arv(a->esq);
   else
      if (a->esq==NULL)
	 v=max_arv(a->dir);
      else
      {
	 v_esq=max_arv(a->esq);
	 v_dir=max_arv(a->dir);
	 if (v_esq>v_dir)
	    v=v_esq;
	 else
	    v=v_dir;
      }
   if (v<a->val)
      v=a->val;
   return v;
}



/* 8.d: ver no capítulos 6 */


/* 8.e */

void show_inv_pre(ARV a)
{
   if (a!=NULL)
      {
         show_inv_pre(a->dir);
	 show_inv_pre(a->esq);
	 printf("%d ",a->val);
      }
}


/* OBS: as soluções para árvores que não são binárias,
 mas implementadas através de "listas de filhos" são idênticas: 
 basta substituir a->esq por a->prim e a->dir por a->prox;
*/


/* EX. 15  */

PT ultx(PT l)
{
   PT p,px=NULL;

   for (p=l; p!=NULL; p=p->prox)
      if (p->val=='x')
   px=p;
   return px;
}



