Programação, Algoritmos e Estrutura de Dados em C - Árvores

Prévia do material em texto

Arvore* criaArvore(No *r)
{
 Arvore* t = (Arvore*)malloc(sizeof(Arvore)); //alocando memória para a criação de uma árvore
 t->raiz = r;
 return t;
}
No* criaNo(char i, No *e, No *d)
{
 No* n = (No*)malloc(sizeof(No)); // alocação de memória para a criação de nós
 n->info = i;
 n->esq = e;
 n->dir = d;
 return n;
}
void preOrdem(No*r) //ordem de percorrimento de uma árvore. Nesse caso pre ordem
{ // exitem mais duas maneiras, sendo elas: em ordem e pós-ordem
 if(r!=NULL)
 {
 printf("%c\n", r->info); // r e d
 preOrdem(r->esq);
 preOrdem(r->dir);
 }
}
void EmOrdem(No *r){ // e r d
 if(r != NULL){
 EmOrdem(r->esq);
 printf("%c\n", r->info);
 EmOrdem(r->dir);
 }
}
void inserir(No *r, int num)
{
 if(r==NULL)
 {
 r=(No*)malloc(sizeof(No));
 r->esq=NULL;
 r->dir=NULL;
 r->info=num;
 }
 else
 {
 if(num<r->info)
 inserir(&r->esq, num);
 if(num>r->info)
 inserir(&r->dir, num);
 }
}
int maior_2(int a, int b)
{
 if(a>b)
 return a;
 else
 return b;
}
int altura (No* r) {
	if ((r == NULL) || (r->esq == NULL && r->dir == NULL))
 return 0;
	else
		return maior_2 (altura (r->esq), altura (r->dir)) + 1;
}
int similares (No *r1, No* r2) {
	if (r1 == NULL && r2 == NULL)
		return 1;
	if ((r1 == NULL && r2 != NULL) || (r1 != NULL && r2 == NULL) )
		return 0;
	return similares(r1->esq, r2->esq) && similares(r1->dir, r2->dir);
}
int iguais (No *r1, No* r2) {
	if (r1 == NULL && r2 == NULL)
		return 1;
	if ((r1 == NULL && r2 != NULL) || (r1 != NULL && r2 == NULL) )
		return 0;
	return r1->info == r2->info && iguais(r1->esq, r2->esq) && iguais(r1->dir, r2->dir);
}
int Estritamente_Binaria (No* r) {
	if (r == NULL) return 1;
	if ( (r->esq == NULL && r->dir != NULL) || (r->esq != NULL && r->dir == NULL))
		return 0;
	return Estritamente_Binaria(r->esq) && Estritamente_Binaria(r->dir);
}
No* insere (No* r, char c) {
	if (r == NULL) return criaNo (c, NULL, NULL);
	if (c > r->info)
		r->dir = insere (r->dir, c);
	else
		r->esq = insere (r->esq, c);
	return r;
}
No* busca (No* r, char c) {
	if (r == NULL)
 return NULL;
 if (r->info == c)
		return r;
	if (c < r->info)
		return busca (r->esq, c);
	else
		return busca (r->dir, c);
}
int ehFolhaDaArvore (No* r, char c) {
	No* r1 = busca (r, c);
	if (r1 == NULL) return 0;
	if (r1->esq == NULL && r1->dir == NULL)
		return 1;
	else
		return 0;
}
int quatNos(No *r){
 if(r == NULL)
 return 0;
 else
 return 1 + quatNos(r->esq) + quatNos(r->dir);
}
int soma(No *r)
{
 if (r == NULL)
 return 0;
 else
 return r->info + soma(r->esq) + soma(r->dir);
}
int numElem(No *Raiz){ // contando o número de elentos existentes em uma árvore
 if(Raiz == NULL)
 return 0;
 if(Raiz->esq == NULL && Raiz->dir == NULL)
 return 1;
 return 1 + numElem(Raiz->esq) + numElem(Raiz->dir);
}
int maior_3(int a, int b, int c)
{ //função auxiliar. Parte da função maior.
 if(a>b && a>c)
 return a;
 else
 {
 if(b > c)
 return b;
 else
 return c;
 }
}
int maior (No * r)
{ //Encontra o maior valor de Nó em uma árvore, com auxilio da função maior de 3
 if(r==NULL) // sendo ela funcionál apenas para árvores binárias
 return 0;
 else
 return maior_3(r->info, maior(r->esq), maior(r->dir));
}
int arvoreBi(No *r)
{
 if (r) // verificação de árvore estritamente binária
 {
 if(((!r->dir) && (r->esq)) || (r->dir) && (!r->esq))
	 return 1;
	else
	 return arvoreBi(r->esq) && arvoreBi(r->dir);
 }
 return 0;
}
int maiorValor(No *r)
{
	if((r->dir) && (r->dir->info > r->info))
 	return maiorValor(r->dir);
	else
		return r->info;
}
int menorValor(No *r)
{
	if((r->esq) && (r->esq->info < r->info))
 	return menorValor(r->esq);
	else
		return r->info;
int numFolha(No *r)
{
 if (r!=NULL)
 {
 if((!r->esq) && (!r->dir))
	 return 1 + numFolha(r->dir) + numFolha(r->esq);
	else
	 return 0 + numFolha(r->dir) + numFolha(r->esq);
 }
 else
 return 0;
}
void copia(No *n1, No **n2)
{
 if(n1!=NULL)
 {
 insere(n2, n1->info);
	 copia(n1->dir, n2);
	 copia(n1->esq, n2);
 }
}
int qntNos1Filho(No* r) {
	if (r == NULL)
 return 0;
	if ( (r->esq == NULL && r->dir != NULL) || (r->esq != NULL && r->dir == NULL))
		return 1;
	return qntNos1Filho(r->esq) + qntNos1Filho(r->dir);
}
void verifica(No *r, int i)
{
 if (r!=NULL)
 {
 if(r->info == i)
	 return 0;
 else
 {
 if(r->info < i)
 return verifica(r->dir, i);
 else
 return verifica(r->esq, i);
 }
	return 1;
 } }
int maior_q(No * r, int valor)
{
 if(r==NULL)
 return 1;
 else if(r->info > valor)
 return 0;
 else
 return(maior_q(r->esq, valor)|| maior_q(r->dir, valor));
}
int menor_q(No* r, int valor)
{
 if(r==NULL)
 return 1;
 else if(r->info < valor)
 return 0;
 else
 return(menor_q(r->esq, valor)|| menor_q(r->dir, valor));
}
int ehABB(No * r)
{
 if(r==NULL)
 return 0;
 else if(maior_q(r->esq, r->info)|| menor_q(r->dir, r->info))
 return 1;
 else return(ehABB(r->esq) && ehABB(r->dir));}
int qntNulls(No *r)
{
 if(r!=NULL)
 return 0 + qntNulls(r->dir) + qntNulls(r->esq);
 else
 return 1;
}
void verifica(No *r, int i)
{
 if (r!=NULL)
 {
 if(r->info == i)
	 return 0;
 else
 {
 if(r->info < i)
 return verifica(r->dir, i);
 else
 return verifica(r->esq, i);
 }
	return 1;
 }
}
int main () {
	No* r = NULL;
	r = insere (r, 'D'); //68
	r = insere (r, 'B'); //66
 r = insere (r, 'A');//65
	r = insere (r, 'C'); //67
	r = insere (r, 'F'); //70
	r = insere (r, 'E'); //69
	r = insere (r, 'G'); //71
 //476
	printf("Soma = %d\n\n" , soma(r));
	printf("Altura = %d\n\n", altura(r));
	printf("Numedo de elementos = %d\n\n", numElem(r));
	printf("Filhos unicos = %d\n\n", qntNos1Filho(r));
	printf("media = %d\n\n" , (soma(r)/numElem(r)));
	if(Estritamente_Binaria(r) == 0)
 printf("Não eh estritamente binaria\n\n");
 else
 printf("eh estritamente binaria\n\n");
 printf("Maior valor %c\n\n", maiorValor(r));
 printf("Menor valor %c\n\n", menorValor(r));
 printf("Numero de folhas = %d\n\n", numFolha(r));
	No* r1 = busca (r, 'B');
	No* r2 = busca (r, 'B');
	if (iguais (r1, r2)) {
		printf ("sao iguais\n\n");
	}
	else {printf (" nao sao iguais\n\n");}
	getch();
	return 0;
}