Trabalho de Arvores da Professora Fabiana

Á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