Arvores Homero

1
ED – esquema para tutorial 04
Capítulo 4 – Árvores
[página de abertura]
Ao concluir este capítulo, você deverá ser capaz de:
- compreender o que são as árvores
- conhecer os algoritmos básicos que utilizam as árvores binárias
- representar árvores genéricas por meio de árvores binárias
- utilizar árvores binárias de pesquisa
- fazer balanceamento de árvores binárias de pesquisa

2
4.1 Conceitos
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 árvore são:
- o organograma de uma empresa;
- a divisão de um livro em capítulos, seções, tópicos;
- a árvore genealógica de uma pessoa.
De um modo um pouco mais formal, podemos dizer que uma árvore é um conjunto finito de um ou mais nós, tais que:
a) existe um nó denominado raiz;
b) os demais nós formam m>=0 conjuntos disjuntos s1, s2, ... sm, tais que cada um desses conjuntos também é uma árvore (denominada sub-árvore).
As árvores podem ser representadas de diversos modos, como por exemplo:
a) representação hierárquica
{inserir desenho tirado, ou do livro, ou do CBT}
Neste exemplo, A é a raiz da árvore. Os nós B e C são "filhos" de A, e dão origem a duas sub-árvores, nas quais D e E são "filhos” de B, e F é "filho" de C.
b) representação por conjuntos
{inserir desenho tirado, ou do livro, ou do CBT}
A árvore aqui representada é a mesma do desenho anterior. Neste caso, cada nó é representado por um conjunto formado por seus "filhos".
c) representação por expressão parentetizada
A mesma árvore pode ser representada pela expressão:
(A ( B ( D ( ) E ( ) ) C ( F ( ) ) ) )
Cada conjunto de parêntesis correspondentes contém um nó e seus filhos. Se um nó não tem filhos, ele é seguido por um par de parêntesis sem conteúdo.
d) representação por expressão não parentetizada
Ainda utilizando a mesma árvore, podemos usar a representação abaixo:
A 2 B 2 D 0 E 0 C 1 F 0
Cada nó é seguido por um número que indica a quantidade de filhos