Informática

ESTRUTURA DE DADOS
1. Á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.

1.1. Definições e representações básicas
Uma árvore é uma estrutura de dados que se caracteriza por uma relação de hierarquia entre os elementos que a compõem. 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.
Arvore Binária

Jose João Maria Jorge Carmem

Mário

Claudia

Arvore Ternaria

Direção

Inf.

Adm.

Prod.

Para visualizar esse conceito, pode-se representá-lo graficamente. Há formas diferentes de representações gráficas de uma árvore:

a)

Representação hierárquica

1 de 6

b)

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

c)

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.

( A (B) ( C (D (G) (H)) (E) (F (I)) ) )
d) 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.

A2B0C3D2G0H0E0F1I0

e)

Representação por Endentação (Digrama de Barras)

2 de 6

Pode-se representar uma árvore de muitos outros modos, mas é interessante notar que, dentre os exemplos apresentados, a representação “a)” é a que permite uma melhor visualização, e que será utilizada a partir deste ponto. As representações “c)” e “d)” não permitem boa visualização da estrutura, mas podem ser úteis para guardar em arquivos os dados de uma árvore. Como, por definição, os subconjuntos s1, s2,...,sm são disjuntos, cada nó só