Estrutura de dados

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (464 palavras )
  • Download(s) : 0
  • Publicado : 3 de julho de 2012
Ler documento completo
Amostra do texto
Á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

EC

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 todosos 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)...
tracking img