INF 1007 Programação II  
Aula 14 Árvores Binárias  
Edirlei Soares de Lima  
<elima@inf.puc-rio.br>  
Árvores  
Uma estrutura de dados do tipo árvore permite que dados  
sejam organizados de maneira hierárquica.  
Exemplos: arquivos em diretórios, expressões aritméticas,  
planejamento de rotas...  
Árvores  
Uma árvore é composta por um conjunto de nós tal que:  
existe um r, denominado raiz, com zero ou mais sub-árvores, cujas  
raízes estão ligadas a r;  
os nós raízes destas sub-árvores são os filhos de r;  
os nós internos da árvore são os nós com filhos;  
as folhas ou nós externos da árvore são os nós sem filhos;  
Árvores  
Estrutura de uma Árvore:  
#define N 3  
struct noArvore  
{
int info;  
struct noArvore* filhos[N];  
};  
Árvores Binárias  
Uma árvore binária é uma árvore em que cada nó tem zero,  
um ou dois filhos;  
struct noArvore {  
char info;  
struct noArvore* esq;  
struct noArvore* dir;  
};  
Árvores Binárias  
Exemplo: árvores binárias representando expressões  
aritméticas:  
nós folhas representam operandos;  
nós internos operadores;  
Exemplo: (3+6)*(4-1)+5  
Árvores Binárias  
Árvores Binárias Implementação  
Representação de uma árvore:  
através de um ponteiro para o nó raiz  
Representação de um nó da árvore:  
Estrutura em C contendo:  
a informação propriamente dita (exemplo: um caractere);  
dois ponteiros para as sub-árvores, à esquerda e à direita;  
struct noArvore {  
char info;  
struct noArvore* esq;  
struct noArvore* dir;  
};  
Árvores Binárias Implementação  
Interface do tipo abstrato Árvore Binária: arvore.h  
typedef struct noArvore NoArvore;  
NoArvore* arvore_criavazia(void);  
NoArvore* arvore_cria(char c, NoArvore* e, NoArvore* d);  
NoArvore* arvore_libera(NoArvore* a);  
int arvore_vazia(NoArvore* a);  
int arvore_pertence(NoArvore* a, char c);  
void arvore_imprime(NoArvore* a);  
Árvores Binárias Implementação  
Implementação das funções:  
implementação recursiva, em geral;  
usa a definição recursiva da estrutura;  
Uma árvore binária é:  
uma árvore vazia; ou  
um nó raiz com duas sub-árvores:  
a sub-árvore da esquerda (sae);  
a sub-árvore da direita (sad);  
Árvores Binárias Cria Vazia  
Função arvore_criavazia:  
cria uma árvore vazia;  
NoArvore* arvore_criavazia(void)  
{
return NULL;  
}
Árvores Binárias Cria  
Função arvore_cria:  
cria um nó raiz dadas a informação e as duas sub-árvores, a da  
esquerda e a da direita;  
retorna o endereço do raiz criado;  
NoArvore* arvore_cria(char c, NoArvore* sae, NoArvore* sad)  
{
NoArvore* p = (NoArvore*)malloc(sizeof(NoArvore));  
p->info = c;  
p->esq = sae;  
p->dir = sad;  
return p;  
}
Árvores Binárias Libera  
Função arvore_libera:  
libera memória alocada pela estrutura da árvore;  
as sub-árvores devem ser liberadas antes de se liberar o raiz;  
retorna uma árvore vazia, representada por NULL;  
NoArvore* arvore_libera(NoArvore* a)  
{
if (!arvore_vazia(a)){  
arvore_libera(a->esq); /* libera sae */  
arvore_libera(a->dir);  
free(a);  
/* libera sad */  
/* libera raiz */  
}
return NULL;  
}
Árvores Binárias Vazia  
Função arvore_vazia:  
indica se uma árvore é ou não vazia;  
int arvore_vazia(NoArvore* a)  
{
return a == NULL;  
}
Árvores Binárias Imprime 1  
Função arvore_imprime:  
percorre recursivamente a árvore, visitando todos os nós e  
imprimindo sua informação;  
void arvore_imprime(NoArvore* a)  
{
if (!arvore_vazia(a))  
{
printf("%c ", a->info); /* mostra raiz */  
arvore_imprime(a->esq); /* mostra sae */  
arvore_imprime(a->dir); /* mostra sad */  
}
}
Árvores Binárias Imprime 2  
Função arvore_imprime:  
percorre recursivamente a árvore, visitando todos os nós e  
imprimindo sua informação formatada de acordo com a sua posição  
na árvore;  
void arvore_imprime(NoArvore *a, int nivel)  
{
int n;  
if (arvore_vazia(a))  
return;  
arvore_imprime(a->dir, nivel + 1);  
for (n = 0; n < nivel; n++)  
printf("\t");  
printf("%d\n\n",a->info);  
arvore_imprime(a->esq, nivel + 1);  
}
Árvores Binárias Pertence  
Função arvore_pertence:  
verifica a ocorrência de um caractere c em um de nós;  
retorna um valor booleano (1 ou 0) indicando a ocorrência ou não do  
caractere na árvore;  
int arvore_pertence (NoArvore* a, char c){  
if (arvore_vazia(a))  
return 0;  
else  
/* árvore vazia: não encontrou */  
return a->info==c || arvore_pertence(a->esq,c) ||  
arvore_pertence(a->dir,c);  
}
Árvores Binárias Criação  
/
* sub-árvore 'd' */  
NoArvore* a1= arvore_cria('d',arvore_criavazia(),arvore_criavazia());  
* sub-árvore 'b' */  
NoArvore* a2= arvore_cria('b',arvore_criavazia(),a1);  
* sub-árvore 'e' */  
NoArvore* a3= arvore_cria('e',arvore_criavazia(),arvore_criavazia());  
* sub-árvore 'f' */  
NoArvore* a4= arvore_cria('f',arvore_criavazia(),arvore_criavazia());  
* sub-árvore 'c' */  
NoArvore* a5= arvore_cria('c',a3,a4);  
* árvore 'a' */  
NoArvore* a = arvore_cria('a',a2,a5 );  
/
/
/
/
/
Árvores Binárias Criação  
NoArvore* a = arvore_cria('a',  
arvore_cria('b',  
arvore_criavazia(),  
arvore_cria('d', arvore_criavazia(),  
arvore_criavazia())  
)
,
arvore_cria('c',  
arvore_cria('e', arvore_criavazia(),  
arvore_criavazia()),  
arvore_cria('f', arvore_criavazia(),  
arvore_criavazia())  
)
);  
Árvores Binárias Acrescentando Nós  
a->esq->esq = arvore_cria('x',  
arvore_cria('y',  
arvore_criavazia(), arvore_criavazia()),  
arvore_cria('z',  
arvore_criavazia(), arvore_criavazia())  
);  
Árvores Binárias Liberando Nós  
a->dir->esq = libera(a->dir->esq);  
Árvores Binárias Ordens de Percurso  
Pré-ordem:  
trata raiz, percorre sae, percorre sad;  
exemplo: a b d c e f  
Ordem simétrica:  
percorre sae, trata raiz, percorre sad;  
exemplo: b d a e c f  
Pós-ordem:  
percorre sae, percorre sad, trata raiz;  
exemplo: d b e f c a  
Árvores Binárias Exercício  
Considere uma árvore binária para representar expressões  
aritméticas:  
nós folhas representam operandos;  
nós internos operadores;  
Exemplo: (3+6)*(4-1)+5  
struct noArvore {  
int valor;  
char op;  
struct noArvore* esq;  
struct noArvore* dir;  
};  
Árvores Binárias Exercício  
Considere uma árvore binária para representar expressões  
aritméticas:  
nós folhas representam operandos;  
nós internos operadores;  
Exemplo: (3+6)*(4-1)+5  
struct noArvore {  
int valor;  
char op;  
struct noArvore* esq;  
struct noArvore* dir;  
};  
Árvores BináriasExercício 1  
Crie uma função para imprimir a expressão codificada em um  
árvore binária. A função deve seguir o seguinte protótipo:  
void imprimeExp(NoArvore* a)  
Para o exemplo ao lado, a função deve  
imprimir a seguinte expressão:  
(((3+6)*(4-1))+5)  
struct noArvore {  
int valor;  
char op;  
struct noArvore* esq;  
struct noArvore* dir;  
}
;
Árvores Binárias Exercício 1  
void imprimeExp(NoArvore* a)  
{
if (!arvore_vazia(a))  
{
if (arvore_vazia(a->dir) && arvore_vazia(a->esq))  
printf("%d", a->valor);  
else {  
printf("(");  
arvore_imprimeExp(a->esq);  
printf("%c", a->op);  
arvore_imprimeExp(a->dir);  
printf(")");  
}
}
}
Árvores BináriasExercício 2  
Crie uma função para avaliar a expressão codificada em um  
árvore binária. A função deve seguir o seguinte protótipo:  
float avalia(NoArvore* a)  
Para o exemplo ao lado, o resultado da  
expressão é: 20  
struct noArvore {  
int valor;  
char op;  
struct noArvore* esq;  
struct noArvore* dir;  
}
;
Árvores Binárias Exercício 2  
float avalia(NoArvore* a)  
{
if (arvore_vazia(a->dir) && arvore_vazia(a->esq))  
return a->valor;  
else {  
if(a->op == '+')  
return avalia(a->esq) + avalia(a->dir);  
if(a->op == '-')  
return avalia(a->esq) - avalia(a->dir);  
if(a->op == '*')  
return avalia(a->esq) * avalia(a->dir);  
if(a->op == '/')  
return avalia(a->esq) / avalia(a->dir);  
}
}
Exercícios  
Lista de Exercícios 13 Árvores Binárias  
http://www.inf.puc-rio.br/~elima/prog2/  
Árvore Binária de Busca (ABB)  
O valor associado à raiz é sempre maior  
que o valor associado a qualquer nó da  
sub-árvore à esquerda (sae);  
O valor associado à raiz é sempre menor  
ou igual (para permitir repetições) que o  
valor associado a qualquer nó da sub-  
árvore à direita (sad);  
Quando a árvore é percorrida em ordem  
simétrica (sae - raiz - sad), os valores são  
encontrados em ordem crescente;  
Pesquisa em Árvore Binária de Busca  
Compare o valor dado com o valor  
associado à raiz:  
Se for igual, o valor foi encontrado;  
Se for menor, a busca continua na sae;  
Se for maior, a busca continua na sad;  
Pesquisa em Árvore Binária de Busca  
Em árvores balanceadas os nós internos têm todos, ou quase  
todos, 2 filhos;  
Qualquer nó pode ser alcançado a partir da raiz em O(log n)  
passos;  
Pesquisa em Árvore Binária de Busca  
Em árvores degeneradas todos os nós têm apenas 1 filho, com  
exceção da (única) folha;  
Qualquer nó pode ser alcançado a partir da raiz em O(n) passos;  
Tipo Árvore Binária de Busca  
A árvore é representada pelo ponteiro para o nó raiz:  
struct noArvore {  
int info;  
struct noArvore* esq;  
struct noArvore* dir;  
};  
typedef struct noArvore NoArvore;  
Árvore Binária de Busca - Criação  
Árvore vazia representada por NULL:  
NoArvore* abb_cria(void)  
{
return NULL;  
}
Árvore Binária de Busca - Impressão  
Imprime os valores da árvore em ordem crescente,  
percorrendo os nós em ordem simétrica:  
void abb_imprime(NoArvore* a)  
{
if (a != NULL)  
{
abb_imprime(a->esq);  
printf("%d\n", a->info);  
abb_imprime(a->dir);  
}
}
Árvore Binária de Busca - Busca  
Explora a propriedade de ordenação da árvore;  
Possui desempenho computacional proporcional à altura da  
árvore;  
NoArvore* abb_busca(NoArvore* r, int v)  
{
if (r == NULL)  
return NULL;  
else if (r->info > v)  
return abb_busca(r->esq, v);  
else if (r->info < v)  
return abb_busca(r->dir, v);  
else  
return r;  
}
Árvore Binária de Busca Inserção  
Recebe um valor v a ser inserido;  
Retorna o eventual novo nó raiz da (sub-)árvore;  
Para adicionar v na posição correta, faça:  
se a (sub-)árvore for vazia:  
crie uma árvore cuja raiz contém v;  
se a (sub-)árvore não for vazia:  
compare v com o valor na raiz;  
insira v na sae ou na sad, conforme o resultado da comparação;  
Árvore Binária de Busca Inserção  
NoArvore* abb_insere(NoArvore* a, int v)  
{
if (a == NULL)  
{
a = (NoArvore*)malloc(sizeof(NoArvore));  
a->info = v;  
a->esq = NULL;  
a->dir = NULL;  
}
else if (v < a->info)  
a->esq = abb_insere(a->esq, v);  
else  
a->dir = abb_insere(a->dir, v);  
é necessário atualizar os ponteiros para as sub-árvores  
à esquerda ou à direita ao chamar recursivamente a  
return a;  
função, pois a função de inserção pode alterar o valor  
do ponteiro para a raiz da (sub-)árvore.  
}
Árvore Binária de Busca Inserção  
cria  
insere 6  
insere 4  
insere 8  
insere 2  
insere 5  
insere 1  
insere 3  
insere 7  
insere 9  
Árvore Binária de Busca Inserção  
cria  
insere 6  
insere 4  
insere 8  
insere 2  
insere 5  
insere 1  
insere 3  
insere 7  
insere 9  
insere 6  
Árvore Binária de Busca Inserção  
cria  
insere 6  
insere 4  
insere 8  
insere 2  
insere 5  
insere 1  
insere 3  
insere 7  
insere 9  
insere 6  
Árvore Binária de Busca Inserção  
NoArvore* abb_insere(NoArvore* a, int v)  
{
if (a == NULL)  
{
a = (NoArvore*)malloc(sizeof(NoArvore));  
a->info = v;  
a->esq = a->dir = NULL;  
}
else if (v < a->info)  
a->esq = abb_insere(a->esq, v);  
else if (v > a->info)  
a->dir = abb_insere(a->dir, v);  
return a;  
}
Árvore Binária de Busca Remoção  
Recebe um valor v a ser inserido;  
Retorna a eventual nova raiz da árvore;  
Para remover v, faça:  
se a árvore for vazia:  
nada tem que ser feito;  
se a árvore não for vazia:  
compare o valor armazenado no raiz com v:  
se for maior que v, retire o elemento da sub-árvore à esquerda;  
se for menor do que v, retire o elemento da sub-árvore à direita;  
se for igual a v, retire a raiz da árvore;  
Árvore Binária de Busca Remoção  
Para retirar a raiz da árvore, há 3 casos:  
Caso 1: a raiz que é folha;  
Caso 2: a raiz a ser retirada possui um único filho;  
Caso 3: a raiz a ser retirada tem dois filhos;  
ABB Remoção de Folha  
Caso 1: a raiz da sub-árvore é folha da árvore original:  
libere a memória alocada pela raiz  
retorne a raiz atualizada, que passa a ser NULL  
ABB Remoção de pai de filho único  
Caso 2: a raiz a ser retirada possui um único filho  
libere a memória alocada pela raiz;  
a raiz da árvore passa a ser o único filho da raiz;  
ABB Remoção de pai de dois filhos  
Caso 3: a raiz a ser retirada tem dois filhos  
encontre o N que precede a raiz na ordenação (o elemento mais à  
direita da sub-árvore à esquerda)  
troque o dado da raiz com o dado de N  
retire N da sub-árvore à esquerda (que agora contém o dado da raiz  
que se deseja retirar)  
retirar o nó N mais à direita é trivial, pois N é um folha ou N é um com um  
único filho (no caso, o filho da direita nunca existe)  
NoArvore* abb_retira(NoArvore* r, int v)  
{
NoArvore *t, *f;  
if (r == NULL)  
return NULL;  
else if (r->info > v)  
r->esq = abb_retira(r->esq, v);  
else if (r->info < v)  
r->dir = abb_retira(r->dir, v);  
else { /* achou o nó a remover */  
if (r->esq == NULL && r->dir == NULL) /* nó sem filhos */  
{
free(r);  
r = NULL;  
}
else if (r->esq == NULL) /* nó só tem filho à direita */  
{
t = r;  
r = r->dir;  
free(t);  
}
...  
...  
else if (r->dir == NULL) /* só tem filho à esquerda */  
{
t = r;  
r = r->esq;  
free (t);  
}
else { /* nó tem os dois filhos */  
f = r->esq;  
while (f->dir != NULL)  
{
f = f->dir;  
}
r->info = f->info; /* troca as informações */  
f->info = v;  
r->esq = abb_retira(r->esq, v);  
}
}
return r;  
}
Árvores Binárias de Busca Exercício 1  
Considerando a seguinte estrutura de uma árvore binária:  
struct noArvore{  
int info;  
struct noArvore* esq;  
struct noArvore* dir;  
}
;
typedef struct noArvore NoArvore;  
Implemente uma função que, dada uma árvore binária de busca, retorne a  
quantidade de nós que guardam valores maiores que um determinado  
valor x (também passado como parâmetro). Essa função tem o seguinte  
protótipo:  
int abb_maiores(NoArvore* a, int x);  
Árvores Binárias de Busca Exercício 1  
int abb_maiores(NoABB* a, int x)  
{
int n = 0;  
if(a == NULL)  
return 0;  
if(a->info > x)  
{
n++;  
n = n + abb_maiores(a->esq, x);  
n = n + abb_maiores(a->dir, x);  
}
else{  
n = n + abb_maiores(a->dir, x);  
}
return n;  
}
Leitura Complementar  
Waldemar Celes, Renato Cerqueira, José Lucas  
Rangel, Introdução a Estruturas de Dados, Editora  
Campus (2004).  
Capítulo 13 Árvores  
Capítulo 17 Busca  
Exercícios  
Lista de Exercícios 14 Árvores Binárias de Busca  
http://www.inf.puc-rio.br/~elima/prog2/