Tópicos Eduardo (1)
Árvores
Percurso pós fixado
Inicios pelo nó externo
(folha) mais a esquerda
Os nodos são visitados
após seus descendentes
Percurso préfixado
Incio pela raiz
Os nodos são visitados
Antes de seus descendentes
Altura de um nodo
A altura de uma árvore =
Altura do nodo raiz
Comprimento do caminho
mais longo dele até um
nó folha
Um nodo filho é ancestral
tanto de seu pai (direto)
como de seu avô.
A profundidade da raiz = 0
A profundidade de um nodo
É o nº de seus ancestrais,
excluindo o próprio nodo.
Nodo Interno = Tem 1
ou mais filhos
Nodo Externo ou Folha =
Não tem filhos
Raiz = Elemento do topo
Armazena dados de
forma hierárquica
Tipo abstrato de dados
Arvóres Binárias
Camin. Euler
Inicie pela raiz e va descendo
pela "parede" em direção ao
filho mais a esquerda que deve
ser considerado o 1º
Continue neste "zig-zag"
Após subir um nó, continue
descendo p/ considerar o
proximo ramo
Apos considerar o filho
mais a esquerda, pegue
o proximo no caminho de
Volta (Subindo)
Camin. Interfixado
Inicia no nodo interno
Mais a esquerda
Reinicie no próximo nodo
Visite o filho
à direita
Visite o Pai
Visite seu filho a esquerda
Vista-se da esquerda
para a direita
Própria
Todo nodo interno tem
exatamente 2 filhos
Imprópria
Tem algum nodo com
somente 1 filho
Todo nodo tem, no
máximo 2 filhos
Grafos
Definições
Sumidouro:
Todo vértice cujo grau de
saida é zero.
Fonte:
Todo vértice cujo grau de
entrada é zero.
Grau de saida:
Nº de setas que saem de um
vértice
Grau de entrada:
Número de setas q chegam
a um vértice
Nº de arestas ligadas a
um Véricie
Conectados por linhas chamadas
de arestas ou arcos, que podem
ou não ter direção.
Misto é o grafo que tem tanto
arestas que não apontam p/
nenhuma direção como outras
que apontam.
Grafo não dirigido é aquele que
nehuma de suas arestas aponta
para nenhuma direção
Se todas as arestas apontam
uma direção temos um
Grafo Dirigido
Conjuntos de pontos ou nodos
chamados vérices
