6 - ARVORES - REVISÃO

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
DEQ/EE3 – FUNDAMENTOS DA ESTRUTURA DA INFORMAÇÃO
Departamento de Engenharia Química
Universidade Estadual de Maringá
Leonardo F. Costa
*
*
REPRESENTAÇÃO DE ARVORES
*
*
QUANTOS NÓS POSSUI ESTA ÁRVORE
*
*
QUANTOS NÓS POSSUI ESTA ÁRVORE
Esta árvore possui 12 nós ou vertices
*
*
Arestas
Uma aresta ou arco liga um nó ao outro
*
*
Subárvores
O nó A possui quantas subarvores
*
*
Subárvores
O nó A possui 3 subárvores
*
*
Subárvores
O nó B possui duas subarvores (ramos)
*
*
Folha
Um nó sem descendentes é chamado de folha
*
*
Nó interior
Um nó com descendentes (filhos ou sucessores) é chamado interior 
*
*
Floresta
É um conjunto de árvores
*
*
Grau
Número de descendentes imediatos de um nó é chamado grau desse nó
*
*
Grau
Número de descendentes imediatos de um nó é chamado grau desse nó
*
*
Grau máximo de um nó
O grau máximo atingido pelos nós de uma árvore é o grau desta árvore
O grau desta árvore é 3
*
*
Árvore Completa
Qual a condição para que uma árvore de grau d seja completa (cheia)?
Todos os nós tenham exatamente d filhos exceto as folhas;
Todas as folhas estão na mesma altura
*
*
Pai e irmãos
As raízes das subárvores de um nó X são os filhos de X e X é o pai dos filhos
*
*
Caminho
O caminho entre A e L é: A,D,H,L formada pela sequencia de arestas (A,D), (D,H) e (H,L)
O comprimento do caminho entre A e L é 3
*
*
Antecessores de um nó
Antecessores de um nó são todos os nós no caminho entre a raiz e o respectivo nó;
Os antecessores de K são A, B e E
*
*
Nível e altura
Os níveis dos nós estão no desenho.
B e D – altura 2
K e L – altura 0
*
*
Árvores Perfeitamente Balanceadas
Uma árvore é perfeitamente balanceada se para cada nó, os números de nós em suas subárvores diferem no máximo em uma unidade
*
*
Árvores Perfeitamente Balanceadas
Uma árvore é balanceada se para cada nó, a altura de suas subárvores diferem, no máximo de uma unidade.
*
*
Árvore Ordenada
Uma árvore ordenada é aquela na qual os filhos de cada nó são ordenados;
Essa ordenação é da esquerda para a direita.
*
*
Árvores Binárias
	Uma árvore binária é uma árvore ordenada cuja estrutura pode ser vazia ou possui três componentes:
Uma raiz
Uma subárvore da esquerda
Uma subárvore da direita