/* www.GeeksBR.com */ /* Implementao de rvore binria */ #include
#include /* Cada n armazena trs informaes: nesse caso um nmero
(num), ponteiro para subrvore direita (sad) e ponteiro para
subrvore esquerda (sae).*/ typedef struct tree { int num; struct
tree* sad; struct tree* sae; } Tree; /* A estrutura da rvore
representada por um ponteiro para o n raiz. Com esse ponteiro,
temos acesso aos demais ns. */ /* Funo que cria uma rvore */ Tree*
createTree() { /* Uma rvore representada pelo endereo do n raiz,
essa funo cria uma rvore com nenhum elemento, ou seja, cria uma
rvore vazia, por isso retorna NULL. */ return NULL; } /* Funo que
verifica se uma rvore vazia */ int treeIsEmpty(Tree* t) { /*
Retorna 1 se a rvore for vazia e 0 caso contrrio */ return t ==
NULL; } /* Funo que mostra a informao da rvore */ void
showTree(Tree* t) { /* Essa funo imprime os elementos de forma
recursiva */ printf(""); /* notao para organizar na hora de mostrar
os elementos */ } /* Funo que insere um dado na rvore */ void
insertTree(Tree** t, int num) { /* Essa funo insere os elementos de
forma recursiva */ if(*t == NULL)
{ *t = (Tree*)malloc(sizeof(Tree)); /* Aloca memria para a
estrutura */ (*t)->sae = NULL; /* Subrvore esquerda NULL */
(*t)->sad = NULL; /* Subrvore direita NULL */ (*t)->num =
num; /* Armazena a informao */ } else { if(num < (*t)->num)
/* Se o nmero for menor ento vai pra esquerda */ { /* Percorre pela
subrvore esquerda */ insertTree(&(*t)->sae, num); } if(num
> (*t)->num) /* Se o nmero for maior ento vai pra direita */
{ /* Percorre pela subrvore direita */
insertTree(&(*t)->sad, num); } } } /* Funo que verifica se
um elemento pertence ou no rvore */ int isInTree(Tree* t, int num)
{ if(treeIsEmpty(t)) { /* Se a rvore estiver vazia, ento retorna 0
*/ return 0; } /* O operador lgico || interrompe a busca quando o
elemento for encontrado */ return t->num==num ||
isInTree(t->sae, num) || isInTree(t->sad, num); } /* Funo
para liberar a memria alocada pela rvore */ Tree* freeTree(Tree* t)
{ /* Essa funo tambm usa implementao recursiva */
if(!treeIsEmpty(t)) /* se a rvore no for vazia... */ { /* Tem que
liberar as subrvores primeiro para que o acesso no seja perdido. */
freeTree(t->sae); /* libera a subrvore esquerda */
freeTree(t->sad); /* libera a subrvore direita */ freeTree(t);
/* libera a raiz */ } /* Retorna uma rvore vazia, ou seja, NULL */
return NULL; } int main() { Tree* t = createTree(); /* cria uma
rvore */ insertTree(&t, insertTree(&t, insertTree(&t,
insertTree(&t, 12); 15); 10); 13); /* /* /* /* insere insere
insere insere o o o o elemento elemento elemento elemento 12 15 10
13 na na na na rvore rvore rvore rvore */ */ */ */
showTree(t); /* Mostra os elementos da rvore em pr-ordem */
if(treeIsEmpty(t)) /* Verifica se a rvore est vazia */ {
printf("\n\nArvore vazia!!\n"); } else { printf("\n\nArvore NAO
vazia!!\n"); } if(isInTree(t, 15)) { /* Verifica se o nmero 15
pertence a rvore */ printf("\nO numero 15 pertence a arvore!\n"); }
else { printf("\nO numero 15 NAO pertence a arvore!\n"); }
if(isInTree(t, 22)) { /* Verifica se o nmero 22 pertence a rvore */
printf("\nO numero 22 pertence a arvore!\n\n"); } else {
printf("\nO numero 22 NAO pertence a arvore!\n\n"); } freeTree(t);
/* Libera a memria alocada pela estrutura rvore */ system("pause");
return 0; }
