Árvores e árvores binárias de busca

Prévia do material em texto

1
Estruturas de Dados 
Não-Lineares
(Árvores)
Árvores N-árias
• Definição:
– Uma árvore é um conjunto finito de N ≥≥≥≥ 0
elementos denominados nós ou vértices. 
– Se N = 0, dizemos que a árvore é nula; 
– Se N > 0, então:
• Existe um nó especial denominado raiz da árvore;
• Os demais nós formam conjuntos disjuntos S1, ..., 
Sm, onde cada um destes conjuntos é uma árvore.
• As árvores Si são denominadas subárvores.
Árvores N-árias
• Representação Hierárquica de uma Árvore
A
C
H
L M
B
F GE
K
D
I J
Árvores N-árias
• Exemplo de aplicação:
– Representação da ordem de execução de uma 
expressão aritmética � a + b * (c / d – e)
+
/
c d
a *
e
b -
Árvores N-árias
• Terminologia:
– O grau de um nó é o número de subárvores do 
nó.
– Uma folha (ou nó terminal) é um nó de grau 
zero.
– Um nó dito não-terminal é um nó interno, ou 
seja, que possui subárvores.
– O grau de uma árvore (n-aridade) é o máximo 
dos grau de todos os seus nós.
Árvores N-árias
• Terminologia:
– As raízes das subárvores de um nó denominam-
se filhos do nó, que é o pai delas.
– Nós com um mesmo pai são denominados 
irmãos.
2
Árvores N-árias
• Terminologia (cont.):
– O nível de um nó é a distância dele até a raiz.
– O nível da raiz é zero.
– A altura de um nó é o número de nós do maior 
caminho dele até um de seus descendentes.
– As folhas têm altura zero.
– A altura (ou profundidade) de uma árvore é
igual a altura da raiz da árvore.
– Uma árvore vazia tem altura zero.
Árvores N-árias
• Terminologia (cont.):
– Árvore Ordenada
• É quando a ordem das subárvores é significativa.
A
B C
A
C B
≠≠≠≠
Árvores Binárias
• Definição:
– Uma árvore binária é um conjunto finito de 
N ≥≥≥≥ 0 elementos denominados nós ou vértices. 
– Se N = 0, dizemos que a árvore é nula; 
– Se N > 0, então:
• Existe um nó especial denominado raiz da árvore;
• Os demais nós formam dois conjuntos disjuntos
S1,e S2, onde cada um destes conjuntos é, por 
definição, uma árvore binária.
Árvores Binárias
• Definição:
– Uma árvore binária é uma árvore de grau dois 
ordenada.
– Suas subárvores são denominadas subárvore
esquerda e subárvore direita.
A
B
A
B
≠≠≠≠
Árvores Binárias
• Terminologia:
– Árvore Estritamente Binária
• É quando todos os nós não terminais da árvore 
binária possuem subárvores esquerda e direita não 
vazias.
Árvores Binárias
• Terminologia:
– Árvore Estritamente Binária (Exemplo)
A
B C
D
F G
E
3
Árvores Binárias
• Terminologia:
– Árvore Binária Completa
• Uma árvore binária completa de profundidade D é
uma árvore estritamente binária em que todas as 
folhas estão no mesmo nível.
Árvores Binárias
• Terminologia:
– Árvore Binária Completa (Exemplo)
A
B C
DF G E
Árvores Binárias
• Implementação Encadeada:
typedef struct no {
struct no *dir;
char info;
struct no *esq;
}TNo;
TNo *arvbin;
• Representação:
Árvores Binárias
E
B J
A D G L
ARVBIN
• Passeio em árvores binárias
– Por passeio entende-se uma visita sistemática a 
cada um dos nós da árvore.
– Visitar um nó significa operar, de alguma 
forma, com a informação nele contida.
– Formas de passeio:
• Em-ordem
• Pré-ordem
• Pós-ordem
• Por-nível
Árvores Binárias Árvores Binárias
• Passeio Em Ordem
1. Percorrer a subárvore à esquerda
2. Visitar a raiz
3. Percorrer a subárvore à direita
A
B C
D E F G
Em Ordem: D B E A F C G 
4
Árvores Binárias
• Passeio Em-ordem
void emOrdem (TNo * raiz)
{
if (raiz != NULL)
{
emOrdem(raiz->esq);
printf(“%i \n”, raiz->info);
emOrdem(raiz->dir);
}
}
Árvores Binárias
• Passeio Pré-Ordem
1. Visitar a raiz
2. Percorrer a subárvore à esquerda
3. Percorrer a subárvore à direita
A
B C
D E F G
Pré-Ordem: A B D E C F G 
Árvores Binárias
• Passeio Pré-ordem
void preOrdem (TNo * raiz)
{
if (raiz != NULL)
{
printf(“%i \n”, raiz->info);
preOrdem(raiz->esq);
preOrdem(raiz->dir);
}
}
Árvores Binárias
• Passeio Pós-Ordem
1. Percorrer a subárvore à esquerda
2. Percorrer a subárvore à direita
3. Visitar a raiz
A
B C
D E F G
Pós-Ordem: D E B F G C A 
Árvores Binárias
• Passeio Pós-ordem
void posOrdem (TNo * raiz)
{
if (raiz != NULL)
{
posOrdem(raiz->esq); 
posOrdem(raiz->dir);
printf(“%i \n”, raiz->info);
}
}
Árvores Binárias
• Passeio Por Nível
A
B C
D E F G
Por Nível: A B C D E F G 
5
Árvores Binárias
• Passeio por Nível
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(“%i \n”, aux->info);
}
}
}
Árvores Binárias de Busca
• Definição:
– Uma árvore binária, cuja raiz armazena o 
elemento R, é denominada árvore de busca 
binária se:
• Todo elemento armazenado na subárvore da 
esquerda for menor que R;
• Nenhum elemento armazenado na subárvore da 
direita é menor que R;
• As subárvores direita e esquerda também são ABB.
Árvores Binárias de Busca
• Exemplo: 
D
B E
A C D F
• Operações Básicas:
– Inserção
• Em uma árvore de busca binária, os elementos 
inseridos entram sempre na condição de folha.
• Se a árvore não estiver vazia e o elemento a inserir 
for menor que a raiz, este será inserido na subárvore
da esquerda;
• Caso contrário, será inserido na subárvore da direita.
Árvores Binárias de Busca
• Implementação:
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);
}
Árvores Binárias de Busca
• Operações Básicas:
– Busca: Considere uma árvore T e um elemento X. 
• T é uma árvore nula: busca impossível;
• A raiz de T armazena o elemento X: solução trivial;
• O valor de X é menor que o valor armazenado na raiz de 
T: prosseguir com a busca na subárvore esquerda de X.
• O valor de X é maior que o valor armazenado na raiz de 
T: prosseguir com a busca na subárvore direita de X.
Árvores Binárias de Busca
6
• Implementação:
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);
}
Árvores Binárias de Busca
• Operações Básicas:
– Remoção: Considere que o elemento a ser 
removido encontra-se na raiz de uma árvore T .
• A raiz não possui filhos: remover a raiz e anular T;
• A raiz possui um único filho: remover a raiz e substituí-
la por seu filho;
• A raiz possui dois filhos: escolher o nodo que armazena 
o maior elemento na subárvore esquerda e substituir a 
raiz por ele.
Árvores Binárias de Busca
Árvores Binárias de Busca
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 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 osfilhos
{
pos = maior(&((*raiz)->esq));
(*raiz)->info = pos->info;
}
free pos;
}
Árvores Binárias de Busca
Árvores Binárias de Busca
TNo * maior(TNo **raiz)
{
TNo * aux;
aux = *raiz;
if (aux->dir == NULL)
{
*raiz = (*raiz)->esq;
return (aux);
}
else
return maior(&((*raiz)->dir));
}