Árvores

6 - ÁRVORES 2

6.1 - CONCEITOS PRELIMINARES 2

Nomenclatura: 2

Representação de Árvores 3

Representação por parênteses 3

Outras representações 3

6.2 - ÁRVORES BINÁRIAS 4

Definições 4

Representação seqüencial em memória 5

Representação por encadeamento 6

Caminhamento ou percurso sobre árvores binárias. 7

Tipos de registros usuais para os nós das árvores 9

Algoritmos Recursivos 9

Algoritmos Não Recursivos 10

Tipos de registros para percurso pós fixo 10

Impressão 13

Montagem de árvores binárias 14

Algoritmos 14

6.3 - ÁRVORES BINÁRIAS COSTURADAS 16

Definições 16

Tipos de registros para os nós das árvores neste caso 17

Algoritmos de Percurso 18

6.4 - OUTRAS FORMAS DE REPRESENTAÇÃO DE ÁRVORES 22

Notação Decimal de Dewey 22

6.5 - REPRESENTAÇÃO DE ÁRVORES POR ÁRVORES BINÁRIAS 23

Conceito 23

Algoritmo de representação de uma árvore por uma árvore binária equivalente. 24

Travessia de árvores e florestas 27

Travessia em ordem pré-fixa 27

Travessia em ordem infixa 27

Travessia em ordem pós-fixa 27

6.6 - ÁRVORES DE BUSCA 27

Conceito 27

Inclusão de nós em árvores de busca 28

Exclusão de nós de árvores de busca 28

Algoritmos 28

6.7 - ÁRVORES BALANCEADAS 31

Conceito 31

Balanceamento 31

Exclusão de nós 40

Árvores Binárias Perfeitamente Balanceadas 40

Algoritmos para tratamento de Árvores Binárias Balanceadas 40

6 - ÁRVORES

6.1 - CONCEITOS PRELIMINARES

Definição: Uma árvore T é um conjunto finito de um ou mais nós tais que:

i) Existe um nó especial denominado raiz

ii) Os nós restantes são repartidos em n  0 conjuntos disjuntos T1, T2,...,Tn, sendo os conjuntos Ti também árvores denominadas sub árvores de T.

Exemplo

A, B, ..., M são registros ou nós.

• Nomenclatura:

Raiz é o nó A, no exemplo.

Grau de um nó é o número de sub árvores do nó. No exemplo, D tem grau 3 e M tem grau zero.

Folhas ou nós terminais são nós de grau zero. No exemplo as folhas são: K, L, F, G, M, I, J.

Filhos de um nó são as raízes das sub árvores daquele nó.

Pai de um nó é um nó que antecede imediatamente um nó da árvore. B é pai de E e F; C é pai de G.

Irmãos são filhos do mesmo nó.

Grau de uma árvore é o maior grau de nó da árvore.

O nível da raiz de uma árvore é 1.

O nível dos filhos de um nó de nível i é i + 1.

Altura de uma árvore é o maior nível encontrado na árvore.

Antecedentes ou ancestrais de um nó são os nós encontrados no trajeto ou percurso da raiz até o nó. No exemplo os antecedentes de M são A e D.

Floresta é um conjunto de n  0 árvores disjuntas. Florestas podem ser obtidas eliminando a raiz de uma árvore.

• Representação de Árvores

 Representação por parênteses

A árvore exibida na Fig. 5.1 teria a seguinte representação usando parênteses:

(A(B(E(K, L), F)) , (C (G)), (D(H(M), I, J))))

 Outras representações

A árvore exibida na Fig. 5.2 teria as seguintes representações usando diagramas de Venn e gráficos de barras:

6.2 - ÁRVORES BINÁRIAS

• Definições

Uma árvore binária é um conjunto finito de nós que é vazio ou consiste de uma raiz e de duas árvores binárias disjuntas chamadas de subárvore esquerda e subárvore direita.

Observações:

i) Não existem árvores vazias. Existem árvores binárias vazias

ii) As figuras abaixo indicadas coincidem caso sejam representações de árvores mas divergem caso sejam representações de árvores binárias.

iii) A figura da esquerda, abaixo, representa uma árvore binária incompleta.

iv) A figura da direita, abaixo, representa uma árvore binária completa.

• Representação seqüencial em memória