Trabalho de Arvores da Professora Fabiana
Por: Allan Gomes • 1/10/2019 • Trabalho acadêmico • 303 Palavras (2 Páginas) • 177 Visualizações
Árvores
Conceitos básicos
Uma árvore é um conjunto finito de elementos denominados nós, nodos ou vértices, dependendo do contexto que está sendo utilizado.
Subárvore é um conjunto de nós, sendo que cada um é a raiz de uma subárvore .
Grau de saída é números de filhos de um nó.
Folha é quando o nó tem grau de saída igual a zero.
Interno é o grau de saída diferente de zero.
Grau de uma árvore é máximo grau de saída.
Nível ou profundidade de um nó é número de nós do caminho da raiz até o nó.
Altura é o nível mais alto da arvore.
Floresta é o conjunto de zero ou mais arvores.
Caminho é uma sequência de nós distintos, é a relação de filho para pai ou de pai para filho.
Raiz está presente em todas arvores, ao qual é subordinado todos outros nodos da arvore.
Filhos são todos nós que tem alguma relação de dependência com outro nó acima.
Nível da raiz sempre é 0.
Tipos de arvores
Árvores ordenadas tem os filhos de cada nó de forma ordenada, sua ordenação vai da esquerda para direita.
Árvores isomorfas são quando temos duas arvores que coincidem segundo a ordenação existente entre os nós
Árvore balanceada(cheia) é quando possui o número máximo de nós. Todos nós tem que ter o número máximo de filhos com exceção das folhas, e todas folhas tem que ter a mesma altura.
Árvore binaria é quando apresenta no máximo grau e em cada nó.
Formas de percorrer a arvore
Percorrer uma arvore tem como objetivo consultar ou alterar alguma informação contida nela.
No caso das arvores binárias existem 3 tipos mais utilizados:
Pré-ordem
- Visitar a raiz
- Percorrer a subárvore da esquerda
- Percorrer a subárvore da direita
In-ordem
- Percorrer a subarvore da esquerda
- Visitar a raiz
- Percorrer a subarvore da direita
Pós-ordem
- Percorrer a subarvore da esquerda
- Percorrer a sub arvore da direita
- Visitar a raiz
...