Árvores Binárias
Estrutura de Dados
Marco Antonio Montebello Júnior
[email protected]
Fundamentos sobre árvores



Uma árvore é um conjunto finito de n >= 0 nós
Se n = 0 temos uma árvore nula
Se n > 0 temos uma árvore com as seguintes
características:



Existe um nó especial chamado raiz;
Os demais são particionados em T1, T2, . . ., Tk
estruturas disjuntas de árvores
As estruturas T1, T2, . . ., Tk denominam-se árvores
Estrutura de Dados
Conceitos importantes sobre
árvores
Grau
A.

Representa o número de subárvores de um nó.
Nó folha ou terminal
B.

É o nó que possui grau 0, ou seja, não possui subárvores.
Grau de uma árvore (n-aridade)
C.

É definido como sendo igual ao máximo dos graus de todos
os seus nós.
Nós filhos
D.

São as raízes das subárvores de um nó. E este nó é o pai
delas.
Estrutura de Dados
Conceitos importantes sobre
árvores
Nós irmãos
E.

São os nós filhos que apresentam o mesmo pai (existem ainda
nó ancestral, descendente, descendente esquerdo ou direito);
Nível
F.

A raiz da árvore tem nível 0 (em alguns livros é considerado
igual à 1). Qualquer outro nó apresenta um nível a mais que
seu nó pai
Altura (em alguns livros é profundidade)
G.

É o máximo dos níveis de todos os nós da árvore. Isso
equivale ao tamanho do passeio mais distante da raiz até
qualquer folha
Estrutura de Dados
Conceitos importantes sobre
árvores
Estrutura de Dados
Conceitos importantes sobre
árvores
Conceito
Valor
A
B
C
D
E
F
G
Estrutura de Dados
Conceitos importantes sobre
árvores
Conceito
Valor
A
Nó ‘a’ grau 3. Nó ‘h’ grau 2
B
‘e’, ‘g’, ‘k’, ‘l’, ‘m’, ‘i’, e ‘j’
C
Grau 4
D
‘z’, ‘e’, ‘f’ e ‘g’ filhos ‘b’. ‘b’ filho ‘a’
E
‘z’, ‘e’, ‘f’ e ‘g’ mesmo pai ‘b’
F
‘b’, ‘c’ e ‘d’ nível 1. ‘z’, ‘e’, ‘f’, ‘g’, ‘h’, ‘i’ e ‘j’ nível
2. ‘k’, ‘l’ e ‘m’ nível 3
Altura: 4
G
Estrutura de Dados
Árvores Binárias

É uma árvore que pode ser nula, ou então
apresentar as seguintes características:



Um nó especial chamado raiz;
Os demais nós são particionados em T1, T2
estruturas disjuntas de árvores binárias;
A estrutura T1 é chamada subárvore esquerda e T2
subárvore direita da raiz.
Estrutura de Dados
Árvores Binárias

Árvore binária estritamente binária


Ocorre quando todo nó que não é folha, tiver
subárvores esquerda e direita não vazias. Uma árvore
estritamente binária com n folhas contém sempre
2n - 1 nós
Árvore binária completa

É uma árvore estritamente binária de profundidade
(altura) d, cujas folhas estejam no nível n.
Considerando tn como o número total de nós numa
árvore binária completa de profundidade d,
observamos a seguinte relação : tn = 2d - 1
Estrutura de Dados
Observações importantes




Observamos que uma árvore binária é um caso
especial de árvore cujos nós não têm grau
superior a 2
Nenhum nó tem mais do que dois filhos
Existe um forte senso de posição pela existência
de uma subárvore direita e esquerda
Cada subárvore caracteriza uma definição
recursiva
Estrutura de Dados
Observações importantes

Será que as árvores binárias apresentadas
abaixo são iguais ou distintas? Por que?
Exemplo de duas árvores binárias com subárvores nulas
Estrutura de Dados
Observações importantes
Um exemplo de árvore estritamente binária
Estrutura de Dados
Observações importantes
Um exemplo de árvore binária completa de nível 3 e altura 4
Estrutura de Dados
Árvores de Busca
Binárias
Estrutura de Dados
Marco Antonio Montebello Júnior
[email protected]
Árvores de busca binária

É aquela que tem a propriedade de todos os
elementos na subárvore esquerda de um nó n
serem menores que o conteúdo de n, e todos os
elementos na subárvore direita de n serem
maiores ou iguais ao conteúdo do nó n
Estrutura de Dados
Árvores de busca binária

Dessa forma, podemos realizar as seguinte
observações:




Todo elemento armazenado na subárvore esquerda é
menor que n;
Nenhum elemento armazenado na subárvore direita é
menor que n;
As subárvores esquerda e direita também são árvores
de busca binária
A definição de árvore de busca binária também é
recursiva
Estrutura de Dados
Árvores de busca binária

Abaixo está o exemplo de uma árvore de busca binária
e uma árvore que não pode ser considerada como tal.
Árvores Binárias ordenada
(busca binária)
Árvore Binária não ordenada
Estrutura de Dados
Mais um Exemplo de Árvore de
Busca Binária

Veja mais um exemplo de árvore de busca binária, dessa vez, com valores
numéricos e considerando a seguinte seqüência de entrada : 14, 15, 4, 9, 7, 18,
3, 5, 16, 4, 20, 17, 9, 14 e 5.
Estrutura de Dados
Outro exemplo

Uma outra aplicação é a representação de uma
expressão contendo operandos e operadores
A+B*C
(A + B) * C
Estrutura de Dados
Operações básicas em árvores
de busca binária

Representando um nó:
struct arv
{
char obj;
struct arv *esq, *dir;
};
typedef struct arv *AVRPTR;
Estrutura de Dados
Operações básicas em árvores
de busca binária




Uma árvore binária de busca binária vazia é
representada por uma variável ponteiro nula
A utilização de uma lista encadeada tem a vantagem de
não necessitar nenhuma movimentação de dados
quando um novo elemento precisa ser inserido
Basta o ajuste adequado dos ponteiros para colocar o
novo elemento na posição adequada
Observamos que a inserção de elementos novos é
ainda mais eficiente porque eles entram sempre na
condição de folhas, pois, um nó não pode entrar numa
árvore e já “assumir” filhos
Estrutura de Dados
Operações básicas em árvores
de busca binária

Abaixo está a estrutura de representação interna de
uma árvore de busca binária na memória:
Representação interna de árvore binária
Estrutura de Dados
Inserção de um elemento numa
árvore de busca binária

Acompanhe as operações de inserção realizadas na
árvore de busca binária, para observar que basta
movimentar adequadamente os ponteiros para a
realização das inserções
Estrutura de Dados
Inserção de um elemento numa
árvore de busca binária
Estrutura de Dados
Observações sobre a inserção de
elementos numa árvore de busca binária


Observando os exemplos anteriores, podemos
considerar que a inserção é uma operação trivial
Basta verificar se a árvore não está vazia, em
seguida, se o novo elemento é menor do que a
raiz, a inserção é na subárvore esquerda, caso
contrário, a inserção é na árvore direita
Estrutura de Dados
Exemplo de uma rotina para inserir
elementos numa árvore binária de busca
void tins(AVRPTR *plist, char x)
{
if((*plist)== NULL)
{
*plist=(AVRPTR) malloc(sizeof(struct arv));
(*plist)->obj= x;
(*plist)->esq=NULL;
(*plist)->dir=NULL;
}
else
{
if(x<(*plist)->obj)
tins(&((*plist)->esq),x);
else
tins(&((*plist)->dir),x);
}
}
Estrutura de Dados
Pesquisa de um elemento

T é uma árvore nula


A raiz de T armazena o elemento X


A solução é imediata
X é menor que o valor da raiz de T


Não fazemos nada
Prossegue-se com a busca na subárvore esquerda de
T
X é maior ou igual à T

Prossegue-se com a busca na subárvore direita de T
Estrutura de Dados
Exemplo de uma rotina para pesquisar
um elemento numa árvore de busca
binária
AVRPTR tfnd(AVRPTR *plist, char x)
{
if(*plist==NULL)/*elemento nao encontrado*/
return (NULL);
else
if(x==(*plist)->obj)/*elem. encontrado na raiz*/
return(*plist);
else
if(x<(*plist)->obj)/*procura-o numa subarvore*/
return(tfnd(&((*plist)->esq),x));
else
return(tfnd(&((*plist)->dir),x));
}
Estrutura de Dados
Pesquisa de um elemento


Quando os elementos que a árvore armazena
estão distribuídos de forma equilibrada em todas
as subárvores, a busca binária aproxima-se
muito, em eficiência, da busca binária realizada
em tabelas seqüenciais.
Por que?
Estrutura de Dados
Remoção de um elemento

A raiz não possui filhos


A raiz possui um único filho


A solução é imediata. Podemos removê-la e anular T
Podemos remover o nó raiz, substituindo-o pelo seu
nó filho;
A raiz possui dois filhos

Não é possível que os dois filhos assumam o lugar do
pai; escolhemos então o nó que armazena o maior
elemento na subárvore esquerda de T, este nó será
removido e o elemento armazenado por ele entrará
na raiz da árvore T
Estrutura de Dados
Exemplo de uma rotina para remover um
elemento numa árvore de busca binária
AVRPTR getmax(AVRPTR *plist)
{
AVRPTR t;
t = *plist;
if(t->dir == NULL)
{
*plist = (*plist)->esq;
return(t);
}
else
return(getmax(&((*plist)->dir)));
}
Estrutura de Dados
Exemplo
p = getmax(&(t->esq));/*desliga o nó com maior valor*/
t->obj = p->obj;/*armazena o valor na raiz da árvore*/
free(p);
Estrutura de Dados
Uma rotina de remoção mais
genérica


A rotina tRem( ) é essencialmente igual àquele
utilizado para pesquisa
A diferença é que, caso o elemento seja
encontrado (na raiz da árvore), ele será
removido
Estrutura de Dados
Uma rotina de remoção mais
genérica
int tRem(AVRPTR *plist, char *x)
{
AVRPTR p;
if(*plist == NULL)
return(1); /*elemento não encontrado*/
if((*x == (*plist)->obj) == 1) /*elem. encontrado na raiz*/
{
p = *plist;
if((*plist)->esq == NULL)
*plist = (*plist)->dir; /*raiz nao tem filho esq.*/
else
if((*plist)->dir == NULL)
*plist = (*plist)->esq; /*a raiz nao tem filho dir.*/
else /*a raiz tem ambos os filhos*/
{
p = getmax(&((*plist)->esq));
(*plist)->obj=p->obj;
}
free(p);
printf("\nElemento achado e removido!!!");
}
else
if((*x<(*plist)->obj) == 1)
tRem(&((*plist)->esq), x); /*procura na subarvore esq.*/
else
tRem(&((*plist)->dir), x); /*procura na subarvore dir.*/
Estrutura de Dados
}
Passeio em Árvores
Binárias
Estrutura de Dados
Marco Antonio Montebello Júnior
[email protected]
Passeio em árvores binárias
(percurso ou atravessamento)


Realizar um passeio numa árvore binária deve
ser entendido como visitar de forma sistemática,
cada um de seus nós, desenvolvendo um certo
processamento.
Podemos considerar quatro tipos de passeios:




Em-ordem
Pré-ordem (também conhecido como passeio em
profundidade)
Pós-ordem
Em-nível
Estrutura de Dados
Facilitando a compreensão com
uma analogia


Para facilitar a compreensão dos três primeiros tipos,
vamos utilizar um analogia com as notações que uma
expressão aritmética pode ser escrita : infixa, prefixa e
pósfixa.
Considerando a expressão infixa A + B, podemos
utilizar a seguinte representação:
+
A
B
Estrutura de Dados
Analogia

A tabela abaixo ilustra as possibilidades de exibir os nós
da árvore anterior:
Tipo da notação
Seqüência
Equivalência de passeio
Exibir a folha esquerda (E)
Infixa
Exibir a raiz (R)
Em-ordem
Exibir a folha direita (D)
Exibir a raiz (R)
Prefixa
Exibir a folha esquerda (E)
Pré-ordem
Exibir a folha direita (D)
Exibir a folha esquerda (E)
Pósfixa
Exibir a folha direita (D)
Exibir a raiz (R)
Estrutura de Dados
Pós-ordem
Resolva:
Formas de Passeio Saídas
B
A
Em-ordem (ERD)
Pré-ordem (RED)
C
Pós-ordem (EDR)
Estrutura de Dados
Resultado
Formas de Passeio Saídas
B
A
Em-ordem (ERD)
A, B, C
Pré-ordem (RED)
B, A, C
Pós-ordem (EDR)
A, C, B
C
Estrutura de Dados
Exemplo mais complexo de uma
árvore binária com subárvores
Formas de
Saídas
Atravessamento
D
B
Em-ordem (ERD)
E
Pré-ordem (RED)
A
C
F
Pós-ordem (EDR)
Estrutura de Dados
Resultado
Formas de
Saídas
Atravessamento
D
B
Em-ordem (ERD) A, B, C, D, E, F
E
Pré-ordem (RED) D, B, A, C, E, F
A
C
F
Pós-ordem (EDR) A, C, B, F, E, D
Estrutura de Dados
Observações importantes


Pela análise na figura da representação da
expressão A + B como árvore binária e a
analogia realizada a partir dela, percebemos que
a seqüência básica de acesso ERD pode ser
generalizada
Na verdade, cada subárvore não precisa se
restringir a uma única folha:



Exibir a subárvore esquerda (E)
Exibir a raiz (R)
Exibir a subárvore direita (D)
Estrutura de Dados
+
A
B
Observações importantes



Podemos observar que a seqüência ERD tornouse recursivas
Ambas as subárvores devem ser impressas
também em-ordem e a recursão pára quando
chegamos a subárvores nulas
As seqüências pré-ordem e pós-ordem podem
ser generalizadas segundo o mesmo raciocínio
+
A
Estrutura de Dados
B
Rotina para passeio em-ordem
void emordem(AVRPTR t)
{
if(t != NULL)
{
emordem(t->esq);
printf(" %c,",t->obj);
emordem(t->dir);
}
}
Estrutura de Dados
Rotina para passeio em préordem
void preordem(AVRPTR t)
{
if(t != NULL)
{
printf(" %c,",t->obj);
preordem(t->esq);
preordem(t->dir);
}
}
Estrutura de Dados
Rotina para passeio em pósordem
void posordem(AVRPTR t)
{
if(t != NULL)
{
posordem(t->esq);
posordem(t->dir);
printf(" %c,",t->obj);
}
}
Estrutura de Dados
O passeio tipo em-nível




Parece ser o de mais fácil compreensão
Entretanto, sua implementação é a mais complexa.
Supondo que ele fosse aplicado à árvore da figura
abaixo, obteríamos s seqüência : D, B, E, A, C, F
Observe que agora os nós são acessados, por nível, da
esquerda para a direita
D
B
A
E
C
Estrutura de Dados
F
Desenvolvendo um algoritmo
para o passeio em-nível




Podemos usar uma fila contendo inicialmente
apenas o nós raiz
A partir daí, enquanto a fila não se tornar vazia,
retiramos dela um nós cujos filhos deverão ser
colocados na fila, aí então, o nó retirado da fila
pode ser exibido
Como podemos observar, a rotina emnivel faz
uso de uma fila
Também estão listadas as rotinas para
implementar uma fila circular
Estrutura de Dados
Rotina
void emnivel(AVRPTR t)
{
AVRPTR n;
NODEPTR q;
if(t != NULL)
{
qinit(&q);
insert(&q,t);
while (empty(&q) != 1)
{
n = remove(&q);
if(n->esq != NULL)
insert(&q,n->esq);
if(n->dir!=NULL)
insert(&q,n->dir);
printf(" %c,", n->obj);
}
}
}
Estrutura de Dados
Fila Circular
void qinit(NODEPTR *pq)
{
*pq = NULL;
}
void insert(NODEPTR *pq, AVRPTR x)
{
NODEPTR p;
p =(NODEPTR) malloc(sizeof (struct fila));
p->info=x;
if(empty(pq) == 1)
*pq=p;
else
p->next=(*pq)->next;
(*pq)->next=p;
*pq=p;
}
Estrutura de Dados
Fila Circular
AVRPTR remove(NODEPTR *pq)
{
AVRPTR x;
NODEPTR p;
if(empty(pq) == 1)
{
printf("Underflow da fila\n");
getch();
exit(1);
}
p = (*pq)->next;
x = p->info;
if(p == *pq) /*somente um no' na fila*/
*pq = NULL;
else
(*pq)->next = p->next;
free(p);
return(x);
}
int empty(NODEPTR *pq)
{
return((*pq == NULL)?1:0);
}
Estrutura de Dados
Destruição de uma árvore




A rotina tDestruir() utiliza o atravessamento pré-ordem
e, para cada nó acessado, o processamento consiste
numa comparação que avalia se o elemento
armazenado pelo nó é aquele procurado.
Muitos outros algoritmos importantes no tratamento de
árvores são baseados nestes tipos de atravessamento
Abaixo está o exemplo do algoritmo tDestruir( ), para
destruir árvores
Ele utiliza um atravessamento do tipo pós-ordem, cujo
processamento é a liberação do nó acessado
Estrutura de Dados
Destruição de uma árvore
void tDestruir(AVRPTR *plist)
{
if(*plist != NULL)
{
tDestruir(&((*plist)->esq));
/*libera subarvore esquerda*/
tDestruir(&((*plist)->dir));
/*libera subarvore direita */
free(*plist);
}
}
Estrutura de Dados