arvores binarias

Estruturas de Dados

Módulo 13 - Árvores

9/8/2005

(c) Dept. Informática - PUC-Rio

1

Referências
Waldemar Celes, Renato Cerqueira, José Lucas Rangel,
Introdução a Estruturas de Dados, Editora Campus
(2004)
Capítulo 13 – Árvores

9/8/2005

(c) Dept. Informática - PUC-Rio

2

Tópicos
• Introdução
• Árvores binárias
– Representação em C
– Ordens de percurso em árvores binárias
– Altura de uma árvore

• Árvores com número variável de filhos
– Representação em C
– Tipo abstrato de dado
– Altura da árvore
– Topologia binária
9/8/2005

(c) Dept. Informática - PUC-Rio

3

Introdução
•

Árvore
– um conjunto de nós tal que
• existe um nó r, denominado raiz, com zero ou mais sub-árvores, cujas raízes estão ligadas a r
• os nós raízes destas sub-árvores são os filhos de r
• os nós internos da árvore são os nós com filhos
• as folhas ou nós externos da árvore são os nós sem filhos nó raiz

...

9/8/2005

(c) Dept. Informática - PUC-Rio

sub-árvores

4

Árvores binárias
• Árvore binária
– um árvore em que cada nó tem zero, um ou dois filhos
– uma árvore binária é:
• uma árvore vazia; ou raiz • um nó raiz com duas sub-árvores:
– a sub-árvore da direita (sad)

vazia

– a sub-árvore da esquerda (sae)

9/8/2005

(c) Dept. Informática - PUC-Rio

sae

sad

5

Árvores binárias
• Exemplo
– árvores binárias representando expressões aritméticas:
• nós folhas representam operandos
• nós internos operadores

+

• exemplo: (3+6)*(4-1)+5
*

5

+
3

9/8/2005

–
6

(c) Dept. Informática - PUC-Rio

4

1

6

Árvores binárias
• Notação textual:
– a árvore vazia é representada por
– árvores não vazias por
– exemplo:

a b c

d

9/8/2005

e

f

(c) Dept. Informática - PUC-Rio

7

Árvores binárias - Implementação em C
• Representação de uma árvore:
– através de um ponteiro para o nó raiz

• Representação de um nó da árvore:
– estrutura em C