Árvores
Seminário de Matemática Discreta
Componentes: Rogério Caetano Cardoso, Nino Prates
Arcanjo, Leonardo Duarte Vencioneck, Vinicius Maia.
Professor: Leandro Colombi Resendo
Curso: Bacharelado em Sistema de Informação - IFES
Campus Serra
ÍNDICE
Árvores (Definição e terminologias)
2
Árvores Binárias
4
Armazenamento de Árvores Binárias
5
Aplicação
6
Como percorrê-la
6
Algoritmos
6
Exercícios
13
Referências
16
Definição:
Uma árvore T é um conjunto finito de elementos denominados nós ou vértices
tais que: T = 0 é a árvore dita vazia ou existe um nó r, chamado raiz de T; os nós
restantes constituem um único conjunto vazio ou são divididos em m<1 conjuntos
distintos não vazios que são as sub-árvores de r, cada sub-árvore a qual é, por sua vez,
uma árvore.
Exemplo:
Terminologia:
Sub-árvore: Cada nó de árvore é a raiz de uma sub-árvore.
Grau de um nó: O número de sub-árvores de um nó é o grau daquele nó.
Ex: O nó F tem grau 2.
Grau de uma árvore: O grau de uma árvore é o máximo entre os graus de seus nós.
Ex: A árvore acima tem grau 2.
Filhos de um nó X: são as raízes das sub-árvores de um nó.
Ex: O nó D é filho do nó B.
Folha: Um nó de grau igual a zero é denominado folha ou nó terminal.
Ex: As folhas dessa árvore são os nós: D, E, H, I, G.
Nível: A raiz da árvore tem sempre nível 0 e o nível dos demais nós é igual ao número
de linhas que o liga a raiz, isto é o comprimento do caminho que vai da raiz até este nó.
Ex: O nível do nó H é 3.
Altura: É definida pelo nível mais alto da Árvore.
Ex: A tem nível 0; B e C nível 1; D, E, F, G tem nível 2; H e I tem nível 3 e esse é o nivel mais alto,
portanto, a altura da árvore é 3.
Dica: Sempre será uma folha que terá o maior nível da árvore.
Terminologia:
Floresta: É um conjunto de zero ou mais árvores disjuntas.
EX:
Árvore Ordenada: É aquela na qual os filhos de cada nó estão ordenados. Assume – se
a ordenação da esquerda para direita.
Ex:
Ordenada
Não Ordenada
Árvores Isomorfas: Duas árvores não ordenadas são isomorfas quando puderem se
tornar coincidentes através de uma permutação na ordem das sub-árvores de seus nós.
Duas árvores ordenadas são isomorfas quando forem coincidentes segundo a ordenação
existente entre seus nós.
Terminologia:
Árvore Cheia: Árvore com número máximo de nós. Uma árvore de grau x tem número
máximo de nós se cada nó, com exceção das folhas tem grau x.
Ex: Árvore cheia de grau 2:
 Árvore binária:
Árvore binária é aquela em que cada nó tem no máximo duas sub-árvores (filhos),
onde é necessária a distinção entre a da esquerda e a da direita. Árvores binárias são
utilizadas em várias situações, por exemplo, um torneio de futebol eliminatório, do tipo
das copas do mundo, em que a cada etapa os times são agrupados dois a dois e sempre
são eliminados metade dos times é uma árvore binária.
Uma árvore binária pode ser definida como um conjunto finito de nós, que é vazio, ou
consiste de um nó raiz e dois conjuntos disjuntos de nós, a sub-árvore esquerda e a subárvore direita. É importante observar que uma árvore binária não é um caso especial de
árvore e sim um conceito completamente diferente. Observe a figura abaixo e veja que
são duas árvores idênticas, mas são duas árvores binárias diferentes, pois uma tem uma
simples inversão nas folhas da árvore gera duas árvores binárias diferentes.
Existem alguns tipos de árvores binárias:
Árvore estritamente binária: é aquela em que cada nó tem 0 ou 2 filhos.
Árvore binária cheia: é a que se um nó tem alguma sub-árvore vazia então ele está no
último nível.
Árvore binária completa: é a que se n é um nó com algumas de sub-arvores vazias,
então n se está no penúltimo ou no último nível.
Logo, toda árvore cheia é completa e estritamente binária.
Armazenamento de Árvores Binárias (Programação):
Para armazenar cada nó de uma árvore binária precisamos de uma estrutura que
contenha dois ponteiros: um aponta para a sub-árvore esquerda e outro para a subárvore direita. Claro que também devemos ter o campo para o armazenamento das
informações contidas em cada nó. Para armazenar uma árvore com n nós precisamos de
2n+1 unidades de memória.
Exemplo de Aplicação de Árvores Binárias:
Árvores binárias são estruturas importantes toda vez que uma decisão binária
deve ser tomada em algum ponto de um algoritmo. Vamos supor que precisamos
descobrir os números que estão duplicados em uma lista não ordenada de números.
Existem muitas maneiras de se realizar essa tarefa, Uma delas seria comparar cada novo
número com todos os números já lidos, o que aumenta muito a complexidade do
algoritmo. Outra maneira é usar uma árvore binária para manter os números, onde o
primeiro número lido é colocado na raiz da árvore e cada novo número lido é
comparado com o elemento raiz, caso seja igual é uma duplicata e voltamos a ler outro
número. Se for menor repetimos o processo com a árvore da esquerda e se maior com a
árvore da direita. Este processo continua até que uma duplicata é encontrada ou uma
árvore vazia é achada. Neste caso, o número é inserido na posição devida na árvore.
Percorrendo Árvores Binárias
Percorrer uma árvore binária é passar por todos os nós, pelo menos uma vez. Visitar
um nó quer dizer que será executada uma operação com a informação que está
armazenada nesse nó, por exemplo, imprimir seu conteúdo. Quando se percorre uma
árvore binária pode-se passar por alguns nós mais de uma vez, sem porém visitálos.Não existe uma ordem natural para percorrer árvores, logo existem diferentes
maneiras de percorrê-las. Um método é o percurso em pré-ordem, implica em executar
recursivamente os três passos nessa ordem:
1. Visitar a raiz;
2. Percorrer a sub-árvore da esquerda em pré-ordem;
3. Percorre a sub-árvore da direita em pré-ordem.
Para a árvore da figura abaixo este percurso forneceria, no caso da visita significar
imprimir, os seguintes resultados: F B A D C E H G I.
 Algoritmo de Exibição:
void exibirEmOrdem(No *pRaiz){
if(pRaiz != NULL){
exibirEmOrdem(pRaiz->pEsquerda);
printf("\n%i", pRaiz->numero);
exibirEmOrdem(pRaiz->pDireita);
}
}
Esse algoritmo, é um algoritmo recursivo em C, que imprime na tela um nó, com
suas ramificações inferiores. Imprimindo primeiro, todo o ramo da esquerda, pra depois
imprimir as ramificações da direita.

Algoritmo para se contar nós:
int contarNos(No *pRaiz){
if(pRaiz == NULL)
return 0;
else
return 1 + contarNos(pRaiz->pEsquerda) + contarNos(pRaiz->pDireita);
}
Neste algoritmo, ele percorre todos os nós, ou elementos, da árvore, e enquanto
ele existir, ele conta soma esse elemento, com suas ramificações.
 Algoritmo para se contar folhas:
int contarFolhas(No *pRaiz){
if(pRaiz == NULL)
return 0;
if(pRaiz->pEsquerda == NULL && pRaiz->pDireita == NULL)
return 1;
return 0 + contarFolhas(pRaiz->pEsquerda) + contarFolhas(pRaiz->pDireita);
}
Já este algoritmo, soma apenas quando não há ramificações adjacentes ao elemento
passado a ela como parâmetro, no caso, apenas para contar as folhas.
 Algoritmo de Inserção
Para inserirmos valores em uma árvore binária nós utilizamos um procedimento
recursivo que recebe como parâmetro o um nó da arvore e o elemento que vai ser
inserido na árvore. Com isso a árvore é percorrida até que encontremos a posição no
qual o elemento deve ser armazenado e inserimos o mesmo na árvore. Logo abaixo
temos um pseudocódigo com uma estrutura que representa uma arvore binária e o
algoritmo de inserção na mesma.
estrutura No
inicio
inteiro valor;
No dir, esq;
fim
vazio arvore_inserir(No raiz, inteiro valor)
inicio
se(raiz=NULO)
inicio
raiz.valor<-valor;
raiz.esq<-NULO;
raiz.dir<-NULO;
fim se
senao
inicio
se(v>raiz.valor)
inicio
arvore_inserir(raiz.dir,valor);
fim se
senao
inicio
arvore_inserir(raiz.esq,valor);
fim senao
fim senao
fim
 Algoritmo de Remoção
Para removermos um nó de uma árvore devemos levar analisar três casos: o nó não
possui filhos; o nó possui apenas um filho; o nó possui dois filhos. No primeiro caso nós
iremos simplesmente armazenar o valor NULO no nó que será removido.
Removendo nó (8) sem filhos
No segundo o nó filho irá “subir”, ou seja, nós iremos mover o nó filho daquele que será
removido uma posição acima.
Removendo nó (6) com um filho
O terceiro caso é o mais complexo. Aqui nós iremos percorrer a subárvore direita do nó
(ou o filho direito do nó) procurando o elemento mais à esquerda dessa subárvore, ou
seja, o menor elemento. Ao encontrarmos esse elemento, caso ele tenha um filho, esse
filho estará à direita, então esse filho à direita será movido para a posição acima e o pai
será movido para a posição do nó que será removido. Caso o elemento mais à esquerda
não tenha filho então nós simplesmente movemos ele para o nó que será removido e
armazenamos o valor NULO na posição na qual ele se encontrava.
Removendo nó (12) com dois filhos
Um pseudo-código do algoritmo de remoção é mostrado abaixo. Nele nós usamos uma
função auxiliar com o nome percorrer para o caso de um nó com dois filhos. Essa
função percorre a subárvore direita do nó que vai ser removido buscando o elementos
mais à esquerda da mesma, retorna esse elemento e armazena o valor NULO na posição
anterior desse elemento, caso ele não tenha filho ou, caso ele tenha filho, move o filho
uma posição acima. Para esse algoritmo considere a mesma estrutura que foi usada no
algoritmo de inserção para representar a árvore.
vazio arvore_remover(No raiz, inteiro valor)
inicio
inteiro aux;
se(raiz.valor=valor)
inicio
se(raiz.dir=NULO e raiz.esq=NULO)
inicio
raiz<-NULO;
fim se
senao
inicio
se(raiz.esq!=NULO e raiz.dir!=NULO)
inicio
aux=percorrer(raiz.dir);
raiz.valor<-aux;
fim
senao
se(raiz.esq!=NULO)
inicio
raiz.valor<-raiz.esq.valor;
raiz.esq<-NULO;
fim se
senao
inicio
raiz.valor<-raiz.dir.valor;
raiz.dir<-NULO;
fim senao
fim senao
fim senao
fim se
senao
inicio
se(valor>raiz.valor)
inicio
arvore_remover(raiz.dir,valor);
fim se
senao
inicio
arvore_remover(raiz.esq,valor);
fim senao
fim senao
fim
inteiro percorrer(No raiz)
Inicio
inteiro aux;
se(raiz.esq=NULO)
inicio
se(raiz.dir=NULO)
inicio
aux<-raiz.valor;
raiz<-NULO;
retorna aux;
fim se
senao
inicio
aux<-raiz.valor;
raiz.valor<-raiz.dir.valor;
raiz.dir.valor<-NULO;
retorna aux;
fim senao
fim se
senao
inicio
retorna percorrer(raiz.esq);
fim senao
fim
Exercícios:
1) Desenhe a árvore que represente a expressão abaixo: (GERSTING, J. L.,
Fundamentos matemáticos para a ciência da computação, Ed. LTC, 5ª Ed. 2008,
Capítulo 5.2 – exercício 3 ).
[( x – 2 ) * 3 ] + ( 5 + 4 )
Resolução:
2) Monte a árvore binária de acordo com a tabela abaixo: (GERSTING, J. L.,
Fundamentos matemáticos para a ciência da computação, Ed. LTC, 5ª Ed. 2008,
Capítulo 5.2 – exercício 7 [modificado])
Resolução:
3) Dada a árvore abaixo, indique qual elemento é a raiz, os nós e as folhas:
Resolução:
Raiz: A
Nós: B, D, G
Folhas: E, F, C, H, I
Referências:
http://equipe.nce.ufrj.br/adriano/c/apostila/arvore.htm
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein.
Algoritmos: teoria e prática. 2002.
GERSTING, J. L., Fundamentos matemáticos para a ciência da computação, Ed. LTC,
5ª Ed. 2008, Capítulo 5.2