Trabslho

Definições Básicas

Árvores são estruturas de dados extremamente úteis em muitas aplicações. Uma árvore é formada por um conjunto finito T de elementos denominados vértices ou nós de tal modo que se T = 0 a árvore é vazia, caso contrário temos um nó especial chamado raiz da árvore (r), e cujos elementos restantes são particionados em m>=1 conjuntos distintos não vazios, as subárvores de r, sendo cada um destes conjuntos por sua vez uma árvore.

A forma convencional de representar uma árvore está indicado na figura aini abaixo. Esta árvore tem nove nós sendo A o nó raiz.

árvore binária

Figura (aini): Uma árvore

Os conjuntos das subárvores tem de ser disjuntos tem de ser disjuntos portanto a estrutura indicada na Figura arvn não é uma árvore.

Estrutura que não representa árvore

Figura arvn: Estrutura que não representa uma árvore

Se n é um nó da árvore T então Tn indica uma subárvore de T com raiz no nó n. Os nós n1, n2, ..., nk das subárvores de Tn são chamados de filhos de n e n é o pai destes nós, que são nós irmãos. Os nós B e C são filhos de A e nós irmãos. Nós sem filhos como os nós D, H, I, F e G são chamados de folhas. A subárvore da esquerda do nó A tem raiz em B e a subárvore da direita tem raiz em C, isto está indicado pelos dois ramos saindo de A. A ausência de um ramo na árvore indica uma subárvore vazia, como a subárvore da direita do nó B. O número de de filhos de um nó é chamado de grau de saída deste nó. Por exemplo, o nó C tem grau de saída 3 e o nó E grau 2. Se o nó n é a raiz de uma subárvore Tn e n1 pertence a Tn então n1 é descendente de n e n ancestral de n1. Portanto nós sem descendentes próprios é uma folha. Por exemplo, o nó H é ancestral do nó C e o nó D é descendente do nó A.

Um caminho da árvore é composto por uma seqüência de nós consecutivos (n1, n2, ..., nk-1, nk) tal que existe sempre a relação ni é pai de ni+1. Os k vértices formam k-1 pares e um caminho de comprimento igual a k-1. O comprimento do caminho entre o nó A e o nó H é 3.

O nível de um nó n pode ser definido do seguinte modo: o nó raiz tem nível 0, os outros nós tem um nível que é maior uma unidade que o nível de seu pai. Na árvore da figura anterior temos nós nos seguintes níveis:

nível 0 = A

nível 1 = B, C

nível 2 = D, E, F, G

nível 3 = H, I

A altura de um nó n é o número de nós do maior caminho de n até um de seus descendentes. As folhas tem altura 1.

Existem diversas maneiras de representar árvores. Uma representação que reflete a idéia de árvores como conjuntos aninhados é mostrado na figura arvconj abaixo. A figura mostra o mesmo conjunto da figura aini.

Árvores como conjuntos aninhados

Figura (arconj): Árvore representada como conjuntos aninhados.

Uma outra notação que encontramos a toda hora, e que está representada na figura arviden, é a forma identada ou de diagrama de barras. Notar que esta representação lembra um sumário de livro. Os sumários dos livros são representações da árvore do conteúdo do livro.

Árvore representada por identação

Figura (arviden) Árvore e sua representação por barras

Uma outra forma interessante de representar uma árvore é a representação por parênteses aninhados. Da mesma forma que a figura aini representa uma árvore no plano a representação por parênteses representa uma árvore em uma linha. A seqüência de parênteses representa a relação entre os nós da estrutura. O rótulo do nó é inserido à esquerda do abre parênteses correspondente. A árvore representada planarmente pela figura aini pode ser representada em uma linha por

(A (B(D))(C(E(H)(I))(F)(G)))

Esta representação tem importância, por exemplo, no tratamento de expressões aritméticas, já que toda expressão aritmética pode ser colocada nesta forma. Se colocarmos uma expressão nesta forma podemos então representá-la como uma árvore, mostrando como ela seria calculada. Para colocarmos uma expressão em forma de árvore devemos considerar cada operador como um nó da árvore e os seus operandos como as duas subárvores. Considere a expressão C seguinte

A + (B-C)*D%(E*F)

que após receber todos os parênteses fica da seguinte maneira

(A + ((B-C)*(D%(E*F))))

A figura arvexp mostra como fica esta expressão representada por uma árvore.

Expressão e sua representação como árvore

Figura (arvexp) Uma expressão e sua representação como árvore.

------------------------------------------------------------------------

Árvores Binárias

A figura arvbin abaixo mostra um importante tipo de árvore que é a árvore binária. Em uma árvore binária cada nó tem no máximo duas subárvores, e quando há somente uma presente é necessário distinguir entre subárvore esquerda e direita. Árvores binárias podem ser vistas em diversas situações do cotidiano. Por exemplo, um torneio de futebol eliminatório, do tipo das copas dos países, como a Copa do Brasil, em que a cada etapa os times são agrupados dois a dois e sempre são eliminados metade dos times é uma árvore binária.

Figura abin: Árvore binária

Formalmente uma árvore binária pode ser definida como um conjunto finito de nós, que é vazio, ou consiste de um nó raiz e dois conjuntos disjuntos de nós, a subárvore esquerda e a subárvore direita. É importante observar que uma árvore binária não é um caso especial de árvore