Árvores: Estrutura Hierárquica de Dados

Prévia do material em texto

ÁRVORE
- Estrutura de dados que caracteriza uma relação entre os dados que compõem
- A relação existente entre os dados (nós) é uma relação de hierarquia ou de composição, onde um 
conjunto de dados é 
 hierarquizadamente subordinada a outro.
->existe um nó denominado raiz
->os demais formam m>=0 conjuntos disjuntos S1,S2,...,Sm, onde cada um destes nós é uma 
árvore. As árvores Si
- Uma árvore é um conjunto finito T de um ou mais nós, tais que:
(1<=i<=m) recebem a denominação de subárvores.
Terminologias:
-Nó: raiz de uma subárvore
-Grau: número de subárvore de um nó
-Folha: nó de grau zero
-Nível de um nó: número de linhas que liga o nó até a raiz; raiz da árvore tem nível {}
-Altura de uma árvore: nível mais alto da árvore
-Floresta: conjunto de zero ou mais árvores disjuntas
-Árvore ordenada: ordem da subárvore é significativa (árvores a e b são diferentes)
-Árvore orientada (utilizada): ordem das subárvores não é relevante (árvores a e b são iguais)
-Pai: nó raíz das suas subárvores
-Irmãos: raízes das subárvores de um nó
-Filho: raiz da subárvore de um nó pai
Árvore (a) Árvore (b)
Árvores binárias:
1 - representações de dados de forma hierárquica (diretórios, hierarquia de 
organizações)
2 - Representação de expressões aritméticas (a * b + c / (d + e))
aplicações:
-Árvore onde o grau de cada nó é menor ou igual a 2
Árvore
quinta-feira, 3 de julho de 2014
17:14
 Página 1 de Nova Seção 1 
alocação:
->nós representados sequencialmente na memória, de acordo com uma ordem 
convencionada em que eles operam na árvore
->não constitui uma maneira conveniente de representação de árvore na memória dos 
laços
->oferece dificuldade na manipulação da estrutura (inserção, remoção e localização de 
um nó em particular)
A 3 B 1 G 0 C 0 D 2 E 0 F 0
1 - Por adjacência:
->Altamente mais adequada para representação de árvores
->Permite manipulação nos nós com facilidade
->nó alocado dinamicamente (aloque)
-árvore com raiz de graus diferentes
->problema:
-transformar a árvore em árvore binária
->solução:
2 - Encadeada:
 Página 2 de Nova Seção 1