Arvore Binaria

INF1007: Programação 2

10 – Árvores Binárias

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

1

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

• Árvores binária de busca (ABB)
• Funções para ABBs
– Impressão
– Busca

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

2

Tópicos Complementares
• Inserção em ABB
• Remoção em ABB

(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

...

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

sub-árvores

4

Árvores binárias
• um árvore em que cada nó tem zero, um ou dois filhos

• uma árvore binária é:
– uma árvore vazia; ou
– um nó raiz com duas sub-árvores:
• a sub-árvore da direita (sad)

raiz

• a sub-árvore da esquerda (sae) vazia sae

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

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

6

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

4

1

6

Á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 contendo
• a informação propriamente dita (exemplo: um caractere)
• dois ponteiros para as sub-árvores, à esquerda e à direita

struct noArv { char info; struct noArv* esq; struct noArv* dir;
};
(c) Dept. Informática - PUC-Rio

7

Árvores binárias - Implementação em C
• Interface do tipo abstrato Árvore Binária: arv.h typedef struct noArv NoArv;
NoArv* arv_criavazia (void);
NoArv* arv_cria (char