Introdução a Árvores e Árvores
Binárias
Prof. Kariston Pereira
Adaptado de Material gentilmente fornecido pelo
Prof. Rui Tramontin (DCC/UDESC)
Tópicos Abordados

Introdução

Definição de Árvore

Árvores Binárias
UDESC – Prof. Kariston Pereira
2
Introdução

Necessidade de se representar
estruturas de dados hierárquicas.




Estrutura de diretórios
Taxonomias
Organogramas
Sintaxe de expressões
Tais estruturas são
representadas por
Árvores.
UDESC – Prof. Kariston Pereira
3
Introdução

Exemplos: expressão, taxonomia
a + (b * c) / d
Animal
/
Mamífero
+
a
Réptil
d
Primata
*
b
Ave
c
Homem
Cetáceo
Gorila
...
...
Baleia
UDESC – Prof. Kariston Pereira
4
Introdução

Exemplo: sistema de arquivos
UDESC – Prof. Kariston Pereira
5
Tópicos Abordados

Introdução

Definição de Árvore

Árvores Binárias
UDESC – Prof. Kariston Pereira
6
Definição de Árvore

Definição recursiva:



Conjunto de nós.
Existe um nó r denominado raiz, com zero ou mais subárvores, cujas raízes são ligadas diretamente a r.
Os nós raízes das sub árvores são ditos filhos de r.
nó raiz
...
UDESC – Prof. Kariston Pereira
sub-árvores
7
Conceitos Básicos

Grau de saída: número de filhos (sub-árvores) de um nó.

Nó folha: grau de saída = 0.

Nó interno: grau de saída > 0.

Caminho: sequência de nós que tenham relação pai-filho.

Nível de um nó: número de nós no caminho até r.

Altura de árvore: maior nível dentre seus nós.
UDESC – Prof. Kariston Pereira
8
Conceitos Básicos
Grau = 3
A
Nós
internos
B
D
C
Nível = 2
Altura = 3
E
F
I
J
G
H
K
Nós
folhas
UDESC – Prof. Kariston Pereira
9
Tópicos Abordados

Introdução

Definição de Árvore

Árvores Binárias
UDESC – Prof. Kariston Pereira
10
Árvores Binárias


Definição: é a árvore onde todos os seus nós têm
grau <= 2.
Portanto, cada nó pode ter um filho (sub-árvore) à
esquerda e um filho à direira.
UDESC – Prof. Kariston Pereira
11
Tipos de Árvores Binárias




Estritamente Binária: todo nó
interno tem exatamente 2 filhos.
Completa (Cheia): estritamente
binária, e todas as folhas estão no
mesmo nível.
Balanceada: para todo nó, a
diferença de altura de suas subárvores é de no máximo 1.
Degenerada: todos os nós têm
no máximo 1 filho (lista
encadeada).
UDESC – Prof. Kariston Pereira
12
Tipos de Árvores Binárias:
N
Quase Completa

Uma Árvore Binária de
profundidade d será uma
Árvore Binária Quase
Completa se:



N
Cada follha na árvore estiver no
nível d ou no nível d – 1 (até o nível
d – 1 ela é completa);
S
Para cada nó nd na árvore com um
descendente direito no nível d,
todos os descendentes esquerdos
de nd que forem folhas devem
estar ao menos no nível d;
Uma árvore binária quase completa
tem todos os seus níveis completos
exceto o último, o qual pode ter
apenas os elementos mais à
esquerda.
UDESC – Prof. Kariston Pereira
13
Tipos de Árvores Binárias:
N
Quase Completa


Os nós de uma árvore binária
quase completa podem ser
numerados, de modo que seja
atribuído o número 1 à raiz, um
filho esquerdo receba a
atribuição de um número
equivalente ao dobro do número
atribuído ao seu pai, e um filho
direito receba a atribuição de
um número equivalente a um
mais que o dobro do número
atribuído a seu pai.
N
S
Os nós são numerados começando da
raiz, de cima para baixo e da esquerda
para a direita, sem que haja a ausência
de nós.
UDESC – Prof. Kariston Pereira
14
Implementação (1/4)

Nós de uma árvore podem ser representados:



Estaticamente.
Dinamicamente.
Estaticamente, usa-se vetores:

Para cada nó i, seu filho à esquerda está em 2i +
1 e seu filho à direita está em 2i + 2.
UDESC – Prof. Kariston Pereira
15
Implementação (2/4)

Representação Dinâmica:



Nós são implementados como registros (alocados
dinamicamente) ou classes.
Cada nó tem campos que armazenam a informação
propriamente dita e referências a seus nós filhos.
Exemplo em C (quando o percurso é feito sempre de
cima para baixo, da raiz para as folhas):
struct no
{
char info;
struct node *left;
struct node *right;
};
typedef struct no node;
UDESC – Prof. Kariston Pereira
16
Implementação (3/4)

Representação dos nós.
A
A
B
D
E
G
B
C
F
D
C
E
F
G
UDESC – Prof. Kariston Pereira
17
Implementação (4/4)

Funções típicas em uma Árvore Binária:







Inicializar árvore vazia (maketree);
Incluir nó (setleft, setright);
Pesquisar nó (informação);
Excluir nó;
Remover sub-árvore;
Calcular altura da árvore;
Percorrer a árvore (pré-, em-, pós-ordem).
UDESC – Prof. Kariston Pereira
18
Funções Típicas Essenciais
node* maketree(int x)
{
node *p;
p = getnode();
p->info = x;
p->left = NULL;
p->right = NULL;
return (p);
}
setleft (node *p, int x)
{
if (p == null) printf (“inserção vazia\n”);
else if (p->left != NULL)
printf (“inserção incorreta\n”);
else
p->left = maketree(x);
}
setright (node *p, int x)
{
if (p == null) printf (“inserção vazia\n”);
else if (p->right != NULL)
printf (“inserção incorreta\n”);
else
p->right = maketree(x);
}
UDESC – Prof. Kariston Pereira
19
Funções Típicas Essenciais
Algoritmo Exemplo para “Inserção Ordenada Sem Repetição”
int number;
node *tree, *p, *q;
scanf(“%d”, &number);
tree = maketree(number);
while (houver números na entrada)
{
scanf(“%d”, &number);
p = q = tree;
while (number != info(p) && q != NULL)
{
p = q;
if (number < info(p))
q = left (p); //obtem o filho esq. de p
else
q = right (p); //obetem o filho dir. de p
}
if (number == info(p))
printf (“%d %s\n”, number, “está repetido!”);
else if (number < info(p))
setleft (p, number);
else
setright (p, number);
UDESC – Prof. Kariston Pereira
}
20
Travessia em Árvores Binárias

Há várias maneiras de percorrer os nós de uma árvore binária:

Pré-ordem: lê nó, percorre sub-árvore esquerda, percorre sub-árvore
direita


Em-ordem: percorre sub-árvore esquerda, lê nó, percorre sub-árvore
direita


(/ + a * b c d).
(a + b * c / d).
Pós-ordem: percorre sub-árvore esquerda, percorre sub-árvore direita, lê
nó

/
(a b c * + d /).
+
a
d
*
b
c
UDESC – Prof. Kariston Pereira
21
Travessia em Árvores Binárias
void pre_ordem(node *n)
{
if (n != null)
{
processa_info(n->info);
pre_ordem(n->left);
pre_ordem(n->right);
}
}
void em_ordem(node *n)
{
if (n != null)
{
em_ordem(n->left);
processa_info(n->info);
em_ordem(n->right);
}
}
void pos_ordem(node *n)
{
if (n != null)
{
pos_ordem(n->left);
pos_ordem(n->right);
processa_info(n->info);
}
}
UDESC – Prof. Kariston Pereira
22
Aplicações Árvores Binárias

Representação de expressões.

Algoritmos de Ordenação (HeapSort).

Busca (Árvores Binárias de
Busca/Pesquisa).
UDESC – Prof. Kariston Pereira
23
Exercícios




Criar uma Árvore Binária, Incluir alguns
dados e Implementar os algoritmos de
travessia/caminhamento apresentados:
Pré-Ordem;
Em Ordem;
Pós-Ordem.
UDESC – Prof. Kariston Pereira
24