Exemplo de implementação de uma árvore binária de busca

Prévia do material em texto

Exemplo de implementação de uma árvore binária de busca
Arquivo types.h
#ifndef QUEUE
#define QUEUE
typedef struct no {
	struct no * esq;
	char info;
	struct no * dir;
} TNo;
typedef struct noQueue {
	TNo *info;
	struct noQueue * prox;
} NoQueue;
typedef struct descritor {
	NoQueue *inicio, *fim;
} TDescritor;
typedef TDescritor * queue;
#endif
#ifndef TRUE
#define TRUE 1
#endif
#ifndef FALSE
#define FALSE 0
#endif
Arquivo queue.h
#include "types.h"
int isEmpty (queue fila);
void enqueue (queue fila, TNo * valor);
TNo * dequeue (queue fila);
TNo * head (queue fila);
void initialize (queue * fila);
Arquivo queue.c
#include <stdio.h>
#include "types.h"
int isEmpty (queue fila) {
 if (fila->inicio == NULL)
 return TRUE;
 else
 return FALSE;
}
void enqueue (queue fila, TNo * valor) {
 NoQueue * novo;
 novo = (NoQueue *) malloc (sizeof (NoQueue));
 novo->info = valor;
 novo->prox = NULL;
 if (isEmpty (fila) == TRUE)
 fila->inicio = novo;
 else 
 fila->fim->prox = novo;
 fila->fim = novo;
}
TNo * dequeue (queue fila) {
 NoQueue * aux;
 TNo * valor;
 aux = fila->inicio;
 fila->inicio = fila->inicio->prox;
 if (isEmpty (fila) == TRUE)
 fila->fim = NULL;
 valor = aux->info;
 free (aux);
 return valor;
}
TNo * head (queue fila) {
 return fila->inicio->info;
}
void initialize (queue * fila) {
 *fila = (TDescritor *) malloc (sizeof (TDescritor));
 (*fila)->inicio = NULL;
 (*fila)->fim = NULL;
}
Arquivo principal.c
#include <stdio.h>
#include <stdlib.h>
#include "types.h"
#include "queue.h"
void insert(TNo **raiz, char elem);
TNo * find(TNo *raiz, char elem);
void remover(TNo **raiz, char elem);
void remover_no(TNo **raiz);
TNo * maior(TNo **raiz);
void emOrdem (TNo * raiz);
void preOrdem (TNo * raiz);
void posOrdem (TNo * raiz);
void percorrerPorNivel(TNo * raiz);
void removerTodos (TNo ** raiz);
int main () {
	TNo * ABB = NULL, * aux;
	char op, valor;
	do {
		printf ("1 - Inserir \n2 - Remover \n3 - Consultar \n4 - Percorrer em ordem \n");
		printf ("5 - Percorrer pre-ordem \n6 - Percorrer pos-ordem \n7 - Percorrer por nivel \n8 - Encerrar programa \n");
		printf ("Informe a opcao: ");
		op = getchar (); fflush (stdin);
		switch (op) {
		case '1': printf ("Informe o valor: ");
			 valor = getchar(); fflush (stdin);
 insert (&ABB,valor);
				 break;
 case '2': printf ("Informe o valor: ");
			 valor = getchar(); fflush (stdin);
 remover (&ABB,valor);
				 break;
 case '3': printf ("Informe o valor: ");
			 valor = getchar(); fflush (stdin);
 aux = find (ABB,valor);
				 if (aux == NULL)
					 printf ("Valor nao encontrado \n");
				 else
					 printf ("Valor encontrado \n");
				 break;
		case '4': emOrdem (ABB);
			 break;
		case '5': preOrdem (ABB);
			 break;
		case '6': posOrdem (ABB);
			 break;
		case '7': percorrerPorNivel (ABB);
			 break;
		case '8': removerTodos (&ABB);
			 break;
 default: printf ("Opcao invalida \n");
		}
	} while (op != '8');
	return 0;
}
void insert(TNo **raiz, char elem) {
 if (*raiz == NULL)
 {
 *raiz = (TNo *) malloc (sizeof(TNo));
 (*raiz)->info = elem;
 (*raiz)->esq = NULL;
 (*raiz)->dir = NULL;
 }
 else
 if (elem < (*raiz)->info) 
 insert(&((*raiz)->esq),elem);
 else insert(&((*raiz)->dir),elem);
}
TNo * find(TNo *raiz, char elem) {
 if (raiz == NULL)
 return NULL;
 else
 if (elem == raiz->info)
 return raiz;
 else 
 if (elem < raiz->info)
 return find(raiz->esq,elem);
 else return find(raiz->dir,elem);
}
TNo * maior(TNo **raiz) {
 TNo * aux;
 aux = *raiz;
 if (aux->dir == NULL)
 {
 *raiz = (*raiz)->esq;
 return (aux);
 }
 else
 return maior(&((*raiz)->dir));
}
void remover_no(TNo **raiz) {
 TNo * pos;
 pos = *raiz;
 if ((*raiz)->esq == NULL && (*raiz)->dir == NULL) // Não tem filhos
 *raiz = NULL;
 else if ((*raiz)->esq == NULL) // Não tem filho a esquerda
 *raiz = (*raiz)->dir;
 else if ((*raiz)->dir == NULL) // Não tem filho a direita
 *raiz = (*raiz)->esq;
 else // Tem ambos os filhos
 {
 pos = maior(&((*raiz)->esq));
 (*raiz)->info = pos->info;
 }
 free (pos);
}
void emOrdem (TNo * raiz)
{
 if (raiz != NULL)_ {
 emOrdem(raiz->esq);
 printf("%c \n", raiz->info);
 emOrdem(raiz->dir);
 }
}
void preOrdem (TNo * raiz)
{
 if (raiz != NULL)_ {
 printf("%c \n", raiz->info);
 preOrdem(raiz->esq);
 preOrdem(raiz->dir);
 }
}
void posOrdem (TNo * raiz)
{
 if (raiz != NULL)_ {
 posOrdem(raiz->esq); 
 posOrdem(raiz->dir);
 printf("%c \n", raiz->info);
 }
}
�
void remover(TNo **raiz, char elem)
{
 if (*raiz == NULL)
 printf("Elemento não encontrado.\n");
 else if (elem == (*raiz)->info)
 remover_no(&(*raiz));
 else 
 {
 if (elem < (*raiz)->info) 
 remover(&((*raiz)->esq),elem);
 else 
 remover(&((*raiz)->dir),elem);
 }
}
void percorrerPorNivel(TNo * raiz) {
 queue fila;
 TNo * aux;
 if (raiz != NULL) {
 initialize(&fila);
 enqueue (fila,raiz);
 while (isEmpty(fila) == FALSE) {
 aux = dequeue(fila);
 if (aux->esq != NULL)
 enqueue(fila,aux->esq);
 if (aux->dir != NULL)
 enqueue(fila,aux->dir);
 printf("%c \n", aux->info);
 }
 }
}
void removerTodos (TNo ** raiz){
	// implementar como exercicio
}