Aula-EstruturasDados-10f-Arvore-binaria

Árvore Binária – Introdução 1/99
Exemplo de árvore binária
– 39 e 67 são os filhos de 44
– Altura desta árvore é 4
– 67 é a raiz da sub-árvore esquerda de 44

Algoritmos e Estruturas de Dados:
Árvore Binária

44

Raiz

39

Rômulo Silva de Oliveira
Departamento de Automação e Sistemas – DAS – UFSC

20

67
42

60

75

Folha

[e-mail] http://www.das.ufsc.br/~romulo Maio/2011

03

25

Folha
Rômulo Silva de Oliveira, DAS-UFSC, maio/2011

59

65

72

89

Folha

Folha

Folha

Folha

Folha

1

Rômulo Silva de Oliveira, DAS-UFSC, maio/2011

Referências

4

Árvore Binária – Introdução 1/99
Cada nodo da árvore binária contem:
– Dados
– Pointer para nodo filho da esquerda
– Pointer para nodo filho da direita

Mastering Algorithms with C
Kyle Loudon
O´Reilly, 1999

Caso não tenha um filho, NULL é usado para indicar isto
Uma sub-árvore pode ser identificada pelo seu nodo raiz

Livros de algoritmos e estruturas de dados em geral

Um conjunto de árvores é uma floresta

Rômulo Silva de Oliveira, DAS-UFSC, maio/2011

2

Rômulo Silva de Oliveira, DAS-UFSC, maio/2011

Árvore Binária – Introdução 1/99

5

Árvore Binária – Introdução 1/99
Métodos de Caminhamento
Caminhar sobre a árvore significa visitar todos os nodos

Em computação, uma árvore consiste de elementos chamados nodos organizados hierarquicamente
Nodo no topo é a raiz
Os nodos imediatamente abaixo de um certo nodo s ão seus filhos

– Visitar significa acessar o nodo de alguma forma

O método de caminhamento define a ordem das visitas

– Os quais podem ter seus próprios filhos

– No caso de uma lista encadeada não existem muitas opções
– Mas existem várias opções no caso de uma árvore

Com exceção da raiz, cada nodo tem exatamente um nodo pai
O número de filhos que um nodo pode ter depende do tipo da árvore

Métodos mais usuais:
–
–
–
–

– Branching factor

Árvores binárias (binary tree)
–