algoritmo

Algorítmos e estrutura de dados III
Carlos Oberdan Rolim

Ciência da Computação

Árvores - Introdução

* Baseado no material do Prof. Luis Cláudio Gubert

Problemas com listas
Listas ligadas apresentam grande flexibilidade sobre operações contíguas de dados
Sua forte característica sequencial também é o seu ponto fraco Movimentação é feita um nó por vez

Árvores utilizada em muitas aplicações

modela uma hierarquia entre elementos árvore genealógica diagrama hierárquico de uma organização modelagem de algoritmos

O conceito de árvores está diretamente ligado à recursão

Árvores
Uma das mais importantes classes de estruturas de dados em computação são as árvores.
Aproveitando-se de sua organização hierárquica, muitas aplicações são realizadas usando-se algoritmos relativamente simples, recursivos e de eficiência bastante razoável. Definição
Uma árvore é uma estrutura de dados que se caracteriza por uma relação de hierarquia entre os elementos que a compõem.

uma coleção não vazia de vértices e ramos que satisfazem a certos requisitos
Possui uma certa organização

Exemplos de estruturas em forma de árvores são:
O organograma de uma empresa;
A divisão de um livro em capítulos, seções, tópicos, etc;
A árvore genealógica de uma pessoa

Exemplos de árvores

Formas de visualização
Representação hierárquica

Formas de visualização
Representação por conjuntos
(diagrama de inclusão)

Formas de visualização
Representação por expressão parentetizada (parênteses aninhados)
Cada conjunto de parênteses correspondentes contém um nodo e seus filhos.
Se um nodo não tem filhos, ele é seguido por um par de parênteses sem conteúdo.

Formas de visualização
Representação por expressão não parentetizada
Cada nó é seguido por um número que indica a quantidade de filhos desse nodo, e em seguida por esses filhos, representados do mesmo modo.

Formas de visualização
Representação por edentação (diagrama de barras)