/***********
Exercicio 1
**********/


#include "stdlib.h"
#include "conio.h"

typedef struct _No{
	int chave;
	int cont;
	struct _No *esq,*dir;
} No;


void imprime(No *p)
{
	if( p->cont == 1)
		printf("%d(%d vez)\n",p->chave,p->cont);
	else
		printf("%d(%d vezes)\n",p->chave,p->cont);
}

void limpa_arvore(No **p)
{
	if( (*p) != NULL)
	{
		limpa_arvore( &(*p)->esq );
		limpa_arvore( &(*p)->dir );
		free(*p);
		*p = NULL;
	}
}

void inorder(No *p)
{
	if( p != NULL)
	{
		inorder( p->esq );
		imprime(p);
		inorder( p->dir );
	}
}

void insere(int x,No **p)
{
	if(*p==NULL)
	{
		*p=(No*)malloc(sizeof(No));
		(*p)->chave=x;
		(*p)->cont=1;
		(*p)->dir=(*p)->esq=NULL;
	}
	else
	{
		if( x < (*p)->chave )
			insere(x, &(*p)->esq);
		else if( x > (*p)->chave)
			insere(x, &(*p)->dir);
		else //  x == (*p)->chave
			(*p)->cont++;
	}
}


void main()
{
	int n;
	No *raiz=NULL;

	clrscr();
	printf("Digite os numeros 0(zero) para terminar.\n");
	do
	{
		scanf("%d",&n);
		if(n != 0)
		{
			insere(n,&raiz);
			printf("Proximo: ");
		}
	}
	while(n!=0);

	inorder(raiz);
	limpa_arvore(&raiz);

	getch();
}


/***********
Exercicio 2
**********/

/*
	Eu posso obter os elementos em ordem, percorrendo a arvore do modo
	'in-order', pois, pela definicao de arvore binaria de busca, temos que
	todo elemento que esta na sub-arvore esquerda de um noh eh menor do que
	este e todo elemento da sub-arvore direita eh maior. Com isso percorrendo
	da forma 'in-order' iremos percorrer primeiro os elementos menores que a
	raiz, em seguida a propria, e por ultimo os maiores, ou seja, percorrerei
	os elementos em ordem crescente.
*/