Catégories : Tous - dados

par Sidon Duarte Il y a 13 années

208

Tópicos Eduardo

Árvores são estruturas que organizam dados de maneira hierárquica, com uma raiz no topo e nodos que se ramificam em filhos. A altura de um nodo é definida pelo caminho mais longo até uma folha, e a altura da árvore é a altura da raiz.

Tópicos Eduardo

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