Estrutura de dados

Árvores É uma estrutura de dados onde existe uma hierarquia paterna. Existe a relação pai-filho.
- Definição: É um conjunto finito de nós tais que: * Formam uma árvore vazia ou * Existe um nó chamado raiz, os restantes constituem em conjuntos de nós que são as sub-árvores da raiz. - Características: * Um nó não pode ter 2 pais. * Uma árvore não pode haver ciclos. * Cada nó pode ter 0 ou mais filhos. * O nó raiz não tem pai. * Os nós que não têm filhos são chamados de folhas. * Os demais são chamados nós internos. H

G

D

I

F

E

C

A

Exemplo: B

| Raiz | | Nós Internos | | Nós folhas |

Sub-árvores: Árvores filhas de um nó. Ex: Nó A = B e C
Nó C = D, E e F
Nó E = vazia A árvore do exemplo possui 9 sub-árvores. - Filhos: Filhos de um nó. Ex: Nó A -> B e C
Nó D -> G e H * Descendentes próprios.
Ex: Nó C => D, E e F * Rescendentes: Todos os nós abaixo dele.
Ex: Nó A: B, C, D, E, F, G, H, I

- Pai: pai de um nó Ex: Nó E: C * Ancestral próprio: Pai
Ex: nó H: D * Ancestrais: nós que vieram antes.
Ex: nó H: D, C, A

- Irmãos: folhas do mesmo pai.
Ex: nó D: E e F - Caminho de um nó x para o nó y.
São os nós participantes do percurso da árvore do nó X até o nó Y. Ex: caminho A – H: A C D H - Comprimento de um caminho: Número de nós do caminho -1.
Ex: comprimento A – H = 4 – 1 = 3 - Grau de um nó: número de filhos de um nó.
Ex: nó D: 2 - Altura de um nó: é o comprimento mais longo desse nó até um nó folha.
Ex: nó C: 2 - Altura da árvore: altura do nó raiz.
Ex: Nó A: 3 - Profundidade de um nó: comprimento do caminho da raiz até o nó.
Ex: nó F: 2 - Árvore cheia: é quando todos os nós de uma árvore tem o número máximo de filhos, exceto as folhas. Exercícios:

1) Dado a árvore: 7
6
5
4
3
9
8
2
1

15

14

10

13
12
11

a)