Baixe o app para aproveitar ainda mais
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
Compartilhar