Arvore Binaria

Páginas: 10 (2327 palavras) Publicado: 11 de novembro de 2014
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áriasrepresentando 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
• ainformaçã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 c,NoArv* e, NoArv* d);
NoArv* arv_libera (NoArv* a);
int arv_vazia (NoArv* a);
int arv_pertence (NoArv* a, char c);
void arv_imprime (NoArv* a);

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

8

Árvores binárias - Implementação em C
• implementação recursiva, em geral
• usa a definição recursiva da estrutura
Uma árvore binária é:
• uma árvore vazia; ou
• um nó raiz com duas sub-árvores:
– asub-árvore da direita (sad)
– a sub-árvore da esquerda (sae)

raiz
vazia

sae

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

sad

9

Árvores binárias - Implementação em C
• função arv_criavazia
– cria uma árvore vazia

NoArv* arv_criavazia (void)
{
return NULL;
}

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

10

Árvores binárias - Implementação em C
• função arv_cria
– cria um nó raiz dadas ainformação e as duas sub-árvores, a da
esquerda e a da direita
– retorna o endereço do nó raiz criado

NoArv* arv_cria (char c, NoArv* sae, NoArv* sad)
{
NoArv* p=(NoArv*)malloc(sizeof(NoArv));
if(p==NULL) exit(1);
p->info = c;
p->esq = sae;
p->dir = sad;
return p;
}
(c) Dept. Informática - PUC-Rio

11

Árvores binárias - Implementação em C
• criavazia e cria
– as duas funçõespara a criação de árvores
representam
os dois casos da definição recursiva de árvore
binária:
• uma árvore binária NoArv* a;
– é vazia a=arv_criavazia()
– é composta por uma raiz e duas sub-árvores
a=arv_cria(c,sae,sad);

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

12

Árvores binárias - Implementação em C
• função arv_libera
– libera memória alocada pela estrutura da árvore
• as sub-árvoresdevem ser liberadas antes de se liberar o nó raiz

– retorna uma árvore vazia, representada por NULL

NoArv* arv_libera (NoArv* a){
if (!arv_vazia(a)){
arv_libera(a->esq);
/* libera sae */
arv_libera(a->dir);
/* libera sad */
free(a);
/* libera raiz */
}
return NULL;
}
(c) Dept. Informática - PUC-Rio

13

Árvores binárias - Implementação em C
• função arv_vazia
– indica se...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Arvore Binaria
  • Arvore Binaria
  • Árvore Binária
  • Árvore Binária
  • Arvore binaria
  • Arvore binaria
  • Arvore binária
  • Árvore Binária

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!