Capitulo13 17 Exercicios

Estruturas de Dados

Exercícios
Árvores Binárias e Genéricas

6/6/2006

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

1

Exercícios Árvores Binárias
4.2. Implemente uma função que retorne a quantidade de folhas de uma árvore binária. Essa função deve obedecer ao protótipo: int folhas (Arv* a);

4.4. Implemente uma função que compare se duas árvores binárias são iguais.
Essa função deve obedecer ao protótipo:
Arv* igual (Arv* a, Arv* b);

6/6/2006

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

2

Exercícios Árvores Binárias
/* Lista II – Exercício 4.2 */ int folhas (Arv* a)
{
if (arv_vazia(a->esq) && arv_vazia(a->dir)) return 1; else if (!arv_vazia(a->esq) && arv_vazia(a->dir)) return folhas(a->esq); else if (arv_vazia(a->esq) && !arv_vazia(a->dir)) return folhas(a>dir); return folhas(a->esq) + folhas(a->dir);
}

6/6/2006

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

3

Exercícios Árvores Binárias
/* Lista II – Exercício 4.4 */ int igual (Arv* a, Arv* b)
{
return arv_vazia(a) && arv_vazia(b)
||
(!arv_vazia(a) && !arv_vazia(b) && a->info == b->info
&&
igual(a->esq, b->esq)
&&
igual(a->dir, b->dir));
}

6/6/2006

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

4

Exercícios Árvores Binárias

6/6/2006

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

5

Exercícios Árvores Binárias int ocorrencias_x (Arv* a, int x)
{
if (a==NULL) return 0; if (a->info == x) return 1 + ocorrencias_x(a->dir, x); if (a->info < x) return ocorrencias_x(a->dir, x); return ocorrencias_x(a->esq, x);
}

6/6/2006

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

6

Exercícios Árvores Binárias int imprime_folhas (Arv* a)
{
if (a==NULL) return 0; if ((a->esq == NULL) && (a->dir == NULL)) /* imprime só as folhas
*/
{printf(“%d”,a->info); return 1;} imprime_folhas(a->dir); /* em ordem não-crescente */ imprime_folhas(a->esq); }

6/6/2006

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

7

Exercícios Árvores Binárias

6/6/2006

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

8

Exercícios Árvores Binárias

6/6/2006

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

9

Exercícios Árvores Binárias void imprime(Arv* a)
{
/*