progracao orientada a objecto

Universidade de Aveiro
Departamento de Matemática

Algoritmos e Estruturas de Dados

Árvores Binárias

André Marques
Nº Mec. 30380
1

Índice

Introdução …………………………………………………………………………………………………………………………….. 3
Árvores Binárias …………………………………………………………………………………………………………………….. 4
Trabalho Desenvolvido …………………………………………………………………………………………………………… 5
Classe No …………………………………………………………………………………………………………………… 5
Classe ArvoreBinaria ………………………………………………………………………………………………….. 6
Métodos …………………………………………………………………………………………………………………… 7
Métodos implementados relativamente a árvores binárias ordenadas ……………………. 11
Travessias ………………………………………………………………………………………………………………… 17
Complexidade dos algoritmos ………………………………………………………………………………………………..19
Anexos …………………………………………………………………………………………………………………………………. 20
Bibliografia …………………………………………………………………………………………………………………………….27

2

Introdução
As árvores são estruturas de dados extremamente úteis em diversas aplicações, como por exemplo, bases de dados de grandes dimensões, determinação do caminho mais curto entre dois computadores de uma rede, etc. A forma como estas estão organizadas hierarquicamente permite o desenvolvimento de diversas aplicações utilizando-se algoritmos relativamente simples, recursivos e de eficiência bastante razoável.
Mas o que é ao certo um árvore?
Uma árvore é uma estrutura de dados caracterizada por uma relação de hierarquia entre os elementos que a compõem; basicamente, é um tipo de grafo especial em que existe apenas uma origem e não se podem formar ciclos. Matematicamente pode ser definida como um par
(V, E) de dois conjuntos não vazios V-nós (vertex) e E ≤ V2 arestas (edges) que satisfazem duas condições: 


Entre dois nós existe um único caminho;
Um único nó, denominado raiz, só existe como primeiro elemento nos pares de E: os restantes nós são um segundo elemento dos pares de E (podendo também ser primeiro elemento de alguns pares).

Exemplo:

Imagem 1 – retirada de [2]

3