TAD Árvore
Arquivo cabeçalho (tad-arvore.h)
//tad arvore
// definicao da TAD
typedef char TipoChave;
// apontador para o nó da árvore
typedef struct TipoNo * TipoApontador;
// registro para o no
struct TipoNo{
TipoChave chave;
TipoApontador dir, esq;
};
typedef struct TipoNo TipoNo;
// cabecalho para as funcoes
void inicializar(TipoApontador * a);
TipoChave pesquisar(TipoApontador a, TipoChave c);
void inserir(TipoApontador *a, TipoChave c);
void preOrdem(TipoApontador a);
void central(TipoApontador a);
void posOrdem(TipoApontador a);
// definicao das funcoes
void inicializar(TipoApontador * a){
(*a) = NULL;
}
TipoChave pesquisar(TipoApontador a, TipoChave c){
// descricao textual
if (a != NULL){// 1) Se o nó for valido (existente)
if (c == a->chave){// 1.1) Se a chave for igual a chave do no
return c;// 1.1.1) retornar a chave (achei!)
} else// 1.2) caso contrario:
if (c < a->chave){// 1.2.1) Se a chave for menor que a chave do nó
return pesquisar(a->esq, c);// 1.2.1.1) navegar para a esquerda do nó
} else if (c > a->chave){// 1.2.2) Senão se a chave for maior que a chave do no
return pesquisar(a->dir, c);// 1.2.2.1) navegar para a direita do nó
}// 1.2.3) voltar ao passo 1
} else {// 2) Senão (no invalido)
printf("INFO: no nao existe.\n");
return -1;// 2.1) informar que a chave nao existe
}
}
void inserir(TipoApontador * a, TipoChave c){
// descricao textual
if ((*a) == NULL){// 1) se nao houver no (i.e., no nulo)
(*a) = (TipoApontador) malloc(sizeof(TipoNo));// 1.1) criar um novo no
(*a)->chave = c;// 1.2) colocar a chave no novo no
(*a)->dir = NULL;
(*a)->esq = NULL;
}else if (c < (*a)->chave){// 2) se a chave for menor que a chave no no
inserir(&(*a)->esq, c);// 2.1) navegar para a esquerda do no// 2.2) voltar ao passo 1
}else if (c > (*a)->chave){ // 3) se a chave for maior que a chave no no
inserir(&(*a)->dir, c);// 3.1) navegar para a direita do no }// 3.2) voltar ao passo 1
} else {// 4) senao (chave for igual)
printf("INFO: Chave jah existe!\n");// 4.1) a chave jah existe
}
}
void central(TipoApontador a){
if (a == NULL){
return;
}
central(a->esq);
printf("[%c] ", a->chave);
central(a->dir);
}
void preOrdem(TipoApontador a){
if (a == NULL){
return;
}
printf("[%c] ", a->chave);
preOrdem(a->esq);
preOrdem(a->dir);
}
void posOrdem(TipoApontador a){
if (a == NULL){
return;
}
posOrdem(a->esq);
posOrdem(a->dir);
printf("[%c] ", a->chave);
}
Arquivo principal (main.c)
#include <stdio.h>
#include <stdlib.h>
#include "tad-arvore.h"
int main(int argc, char *argv[])
{
TipoApontador a;
TipoChave c;
printf("Inicializacao da arvore:\n");
inicializar(&a); // inicializar a arvore
printf("Conteudo da arvore (CENTRAL):\n");
central(a); printf("\n");
int chaves[] = {'t', 'h', 'e', 'b', 'o', 'o', 'k'}, j;
for (j = 0; j < 7; j++){
c = chaves[j];
inserir(&a, c);
printf("Conteudo da arvore (CENTRAL):\n");
central(a);
printf("\n");
}
printf("Conteudo da arvore (PRE-ORDEM):\n");
preOrdem(a); printf("\n");
printf("Conteudo da arvore (POS-ORDEM):\n");
posOrdem(a); printf("\n");
printf("Pesquisando por 'b':%c\n", pesquisar(a, 'b'));
printf("Pesquisando por 'x':%c\n", pesquisar(a, 'x'));
system("PAUSE");
return 0;
}
Nenhum comentário:
Postar um comentário