Ruan

´ Arvores
Fabr´ J. Barth ıcio
BandTec - Faculdade de Tecnologia Bandeirantes

Setembro de 2011

Disciplina de Estrutura de Dados e Armazenamento

T´picos o
• Introdu¸˜o ca ´ • Arvores bin´rias a Implementa¸˜o em Java ca Ordens de percurso em ´rvores bin´rias a a Altura de uma ´rvore a ´ • Arvores com n´mero v´riavel de filhos u a Implementa¸˜o em Java ca Altura de uma ´rvore a Topologia
´ Arvores — T´picos o Faculdade de Tecnologia Bandeirantes 2

Disciplina de Estrutura de Dados e Armazenamento

´ Introdu¸˜o - Arvore ca
Um conjunto de n´s tal que: o • existe um n´ r, denominado raiz, com zero ou mais o sub-´rvores, cujas ra´ est˜o ligadas a r. a ızes a

´ Arvores —

´ Introdu¸˜o - Arvore ca

Faculdade de Tecnologia Bandeirantes 3

Disciplina de Estrutura de Dados e Armazenamento

• os n´s ra´ destas sub-´rvores s˜o os filhos de r. o ızes a a • os n´s internos da ´rvore s˜o os n´s com filhos. o a a o • as folhas ou n´s externos da ´rvore s˜o os n´s sem o a a o filhos.

´ Arvores —

´ Introdu¸˜o - Arvore ca

Faculdade de Tecnologia Bandeirantes 4

Disciplina de Estrutura de Dados e Armazenamento

´ Arvores Bin´rias a
• uma ´rvore em que cada nodo tem zero, um ou dois a filhos. • uma ´rvore bin´ria ´: a a e uma ´rvore vazia, ou; a um nodo raiz com duas sub-´rvores: a sub-´rvore a a da direita (sad); a sub-´rvore da esquerda (sae). a

´ Arvores —

´ Arvores Bin´rias a

Faculdade de Tecnologia Bandeirantes 5

Disciplina de Estrutura de Dados e Armazenamento

´ Arvores —

´ Arvores Bin´rias a

Faculdade de Tecnologia Bandeirantes 6

Disciplina de Estrutura de Dados e Armazenamento

´ Arvores Bin´rias - Exemplo a
´ Arvore bin´ria representando express˜es aritm´ticas: a o e • n´s folhas representam operandos o • n´s internos operadores o • exemplo: (3 + 6) × (4 − 1) + 5

´ Arvores —

´ Arvores Bin´rias - Exemplo a

Faculdade de Tecnologia Bandeirantes 7

Disciplina de Estrutura de Dados e Armazenamento

+