Funções de Árvore Binária de Busca em C

Prévia do material em texto

/*ABB*/
Funções: Cria / busca / insere / exibeCres /contaMaiores
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct noABB NoABB;
struct noABB
{
	int info;
	NoABB *esq;
	NoABB *dir;
};
NoABB *abb_cria(void)
{
	return NULL;
}
int busca(NoABB *r, int proc)
{
	if(r==NULL)/*Verifica se a ABB é vazia*/
		return 0;
	else
	{
		if(r->info==proc)/*Achou!*/
			return 1;
		if(proc<r->info)/*se a inf procurada for menor que a comparada*/
			return (busca(r->esq,proc));/*voce continua procurando na esquerda*/
		else/*proc>r->info*/
			return(busca(r->dir,proc));/*voce continua procurando na direita*/
	}
}
NoABB * insere(NoABB *r, int novainf)
{
	NoABB *p;
	if(r==NULL)/*A arvore é vazia!*/
	{
		p=(NoABB*)malloc(sizeof(NoABB));
		if(p==NULL)/*erro de alocação*/
			exit(1);
		p->info=novainf;
		p->dir=NULL;
		p->esq=NULL;
		return p;
	}
	else/*a ávore NÃO é VAZIA*/
	{
		if(r->info==novainf)/*a informação ja esta na arvore*/
			return r;/*Retorna a arvore inalterada*/
		if(novainf < r->info)/*se a inf nova for maior que a inf da raiz*/
			r->esq = insere(r->esq, novainf);/*insere na esquerda*/
		else /* novainf > r->info*/
			r->dir = insere(r->dir, novainf);/*insere na direita*/
		return r; /*retorna a raiz*/
	}
}
void exibeCres(NoABB *r)
{
	if(r==NULL)/*Se a arvore for vazia*/
		return;/*Não imprime nada*/
	else/*A arvore é NÃO VAZIA*/
	{
		exibeCres(r->esq);/*IMPRIME A ESQUERDA*/
		printf("%d\n",r->info);/*IMPRIME A RAIZ*/
		exibeCres(r->dir);/*IMPRIME A DIREITA*/
	}
}
int contaMaiores(NoABB *r, int n)
{
	int resp=0;
	if(r==NULL)
		return 0;
	else
	{
		if(r->info>n)
			return 1+contaMaiores(r->esq,n);
		else
			return 0 + contaMaiores(r->esq,n);
	}
}
int main (void)
{
	NoABB *raiz;
	raiz=abb_cria();
	raiz=insere(raiz,10);
	raiz=insere(raiz,9);
	raiz=insere(raiz,31);
	raiz=insere(raiz,65);
	raiz=insere(raiz,29);
	raiz=insere(raiz,12);
	printf("Elementos na arvore\n");
	exibeCres(raiz);
	printf("Existem %d elementos maiores que 20\n", contaMaiores(raiz,20));
	return 0;
}