ÁRVORES

1

ÁRVORES
São estruturas de dados que estabelecem uma relação entre os dados que a compõem. Fundamentos
É um conjunto finito de n nós , com n > 0. Quando n = 0 tem-se uma árvore nula.
Supondo-se que n>0 tem-se uma árvore com as seguintes características:
• Existe um nó especial chamado raiz;
• Os demais nós são particionados em T1, T2, ... Tn estruturas disjuntas de árvores, denominadas subárvores. Como as estruturas são disjuntas, garante-se que um nó não aparecerá em mais de uma subárvore.

Exemplo 1

Exemplo 2

A
A
B

C
D

B

D

C

E

E

F

G

H
I

A árvore representada no exemplo 1 tem como raiz o nó com informação A e duas subárvores B e C. Os nós B, D e E são raízes cujas subárvores respectivas são vazias.

2

Aplicações
A estrutura de árvore é utilizada em casos onde os dados ou objetos a serem representados possuem relações hierárquicas ou de composição entre si.
Grau
Representa o número de subárvores de um nó.

Grau do nó A: _________

Grau do nó F: _________

Grau do nó B: _________

Grau do nó G: _________

Grau do nó C: _________

Grau do nó H: _________

Grau do nó D: _________

Grau do nó I: _________

Grau do nó E: _________

Nó folha ou terminal
É o nó que possui grau 0, ou seja, não possui subárvores.

Nós terminais da árvore do exemplo 2: _______________________
Grau de uma árvore
É definido como sendo igual ao máximo dos graus de todos os seus nós.

Grau da árvore: ____

3

Nós filhos
São as raízes das subárvores de um nó, e este nó é o pai delas.

Filhos do nó A: _________

Filhos do nó F: _________

Filhos do nó B: _________

Filhos do nó G: _________

Filhos do nó C: _________

Filhos do nó H: _________

Filhos do nó D: _________

Filhos do nó I: _________

Filhos do nó E: _________

Nós irmãos
São os nós filhos que apresentam o mesmo pai.

Irmãos do nó A: _________

Irmãos do nó F: _________

Irmãos do nó B: _________

Irmãos do