Implementação de um
mapa através de uma
Árvore Binária de Busca
Árvores Binárias de Busca
Antes de mencionarmos o principal
componente – o Mapa –,
descreveremos as estruturas que
lhe darão suporte, para posterior
desenvolvimento completo do
projeto.
Caraterizaremos cada uma das
terminologias (não universais)
utilizadas para referenciarmos um
determinado nó:
Raiz: nó que não apresenta pai, isto
é, o seu ponteiro father aponta para
NULL.
De forma sucinta, podemos descrever
Nó interno: nó que possui no mínimo
uma árvore como uma estrutura
um ou no máximo dois filhos, por
hierárquica não linear, cujos
estarmos tratando de árvores
elementos estão organizados
binárias.
segundo uma relação de
Nó externo ou folha: não apresenta
descendência.
descendentes.
Sub-árvore: é uma árvore constituída
Sua definição como estrutura, caso
de um nó e de seus descendentes.
não seja vazia, consiste de um
conjunto de nós, referidos por um
nó especial, denominado raiz. Os
demais ou constituem um único
conjunto vazio, ou vários disjuntos
não vazios, cada qual formando
Árvore Binária de Busca
Funções Utilizadas Na Árvore
DefinirArvore():
Replace(T,p,q):
Size(T):
Encontre_Substituto(T,p):
isEmpty(T):
Busca(T,k):
Root(T):
Inserir(T,x):
elem_(T,p):
Remover(T,k):
Parent(T,p):
InOrder(T,p):
leftChild(T,p):
Visit(T,p):
RightChild:
Destroi(T, p):
sibling(T,p):
IsInternal :
isExternal(T,p):
isRoot(T,p):
Swap(T,p,q):
Mapa
Um Mapa é definido como
A implementação deste tipo de
sendo um conjunto de estrutura
estrutura através da inclusão
de dados cujos pares de
do TAD ABB caracteriza a sua
componentes são
definição por uma variável
armazenados de modo que
composta (struct)
uma das informações do par
exclusivamente por um campo
possa ser acessada através de
com um ponteiro para ABB,
uma outra informação, sendo
dada a compatibilidade
que esta última serve à busca.
fornecida pelo conjunto de
Se não é permitido o
operações desta com os
compartilhamento da mesma
principais objetivos do Mapa.
chave por mais de um
elemento, sua caracterização é
plena.
Funções Utilizadas No Mapa
DefinirMapa():
Search(k, M):
Insert(x, M):
Replace(x,M):
Remove(k,M):
DestruirMapa(M):
Descrição do Projeto
Como sabemos, o Mapa.h constitui um Tipo Abstrato de Dados, o qual é definido a partir de
operações que lhe darão suas caraterísticas intrínsecas.
Entretanto o mesmo necessita de outro Tipo Abstrato de Dados, que lhe forneça operações préexistentes que auxiliarão na criação de suas próprias funções principais, permitindo o
armazenamento e organização dos dados inseridos pelo usuário. Deste modo, a configuração
do TAD Mapa requer a inclusão do TAD Árvore Binária de Busca, a qual consta de um
cabeçalho e a implementação das funções descritas pelo mesmo.
Assim, o presente trabalho é dividido em cinco segmentos: programa principal (Main), Mapa.h,
ABB.h e suas respectivas extensões Mapa.c e ABB.c. A seguir, apresentaremos um resumo
sobre a função de cada um dos protótipos de funções que foram construídas para cada
subparte do programa, introduzindo sequencialmente as etapas elaboradas.
Plano de Teste:
Inserção de elementos para teste.
Como deve Ficar...
FIM....

Alunos: Danilo Macan

Thereza Fortunato

Gabriel Cencic