Tipos de Árvores

Estruturas de Dados
Aula 16:
rvores com Nmero Varivel
de Filhos
13/06/2011
Fontes Bibliogrficas
Livros:
Introduo a Estruturas de Dados (Celes,
Cerqueira e Rangel): Captulo 13;
Projeto de Algoritmos (Nivio Ziviani): Captulo 5;
Estruturas de Dados e seus Algoritmos
(Szwarefiter, et. al): Captulo 3;
Algorithms in C (Sedgewick): Captulo 5;
Slides baseados no material da PUC-Rio,

disponvel em http://www.inf.pucrio.br/~inf1620/.
rvore com Nmero Varivel de Filhos

rvore com nmero varivel de filhos:
cada n pode ter mais do que duas sub-rvores associadas
sub-rvores de um n dispostas em ordem
primeira sub-rvore (sa1),
segunda sub-rvore (sa2), etc.
Representao
Em formato textual
<raiz sa1 sa2 ... san>
A rvore exemplo seria representado por

<a <b <c <d>> <e>> <f> <g <h> <i <j>>>>
a
Representao em C
So possveis vrias representaes em C (dependendo
da aplicao)
Por exemplo, em uma aplicao na qual sabe-se que o
nmero mximo de filhos de um dado n 3:
a
struct arv3 {
char info;
struct arv3 *f1, *f2, *f3;
};
c
Representao em C
(cont.)
Funo para imprimir

void arv3_imprime (Arv3* a) {
if (a != NULL){
printf(<%c, a->info);
arv3_imprime (a->f1);
printf(>);
}
}
Note que no h uma maneira sistemtica para acessar

os ns filhos.
Impraticvel declarar um campo para cada filho (imagine
uma rvore com at 100 filhos!)
Representao em C
(cont.)
Uma outra representao possvel

#define N 3
struct arv3 {
char info;
struct arv3 *f[N];
}
void arv3_imprime (Arv3* a){
if (a != NULL){
int i;
printf(<%c, a->info);
for (i=0l i<N; i++)
arv3_imprime (a->f[i]);
printf(>);
} }
Essa abordagem adequada para aplicaes que no se sabe
o nmero de filhos?
Representao em C Adotada
Adequada para representar um nmero varivel de
filhos
Filhos de um n so representados por uma lista
um n aponta para o seu primeiro filho (prim)
cada filho aponta para o prximo (prox) irmo
Representao em C Adotada
Representao de um n da rvore:
a informao propriamente dita (exemplo: um caractere)
ponteiro para a primeira sub-rvore filha
NULL se o n for uma folha
ponteiro para a prxima sub-rvore irmo

NULL se for o ltimo filho
struct arvvar {
char info;
struct arvvar *prim; /* ponteiro para eventual primeiro filho */
struct arvvar *prox; /* ponteiro para eventual irmo */
};
typedef struct arvvar ArvVar;
Definio
Para implementaes recursivas, usar a seguinte
definio:
Uma rvore composta de
Um n raiz; e
Zero ou mais subrvores.
N folha definido como n com zero subrvores

Diferente da definio de folha na rvore binria (folha era n
com subrvores vazias)
Funes no consideram o caso de rvore vazias (prcondio)

Condies de contorno (parada da recurso) devem
considerar essa restrio
10
Exemplo de TADArvVar (TadArvVar.h)

Conjunto de operaes do TAD (usadas como exemplo)
Typedef struct arvvar ArvVar;
Cria um n folha, dada a informao a ser armazenada

ArvVar* arvv_cria (char c);
Insere uma nova subrvore como filha de um dado n

void arvv_insere (ArvVar* a, ArvVar* sa);
Percorre todos os ns e imprime suas informaes

void arvv_imprime (ArvVar* a);
Verifica a ocorrncia de uma dada informao na rvore

int arvv_pertence (ArvVar* a, char c);
Libera toda a memria alocada pela rvore

void arvv_libera (ArvVar* a);
11
Exemplo de TADArvVar
Conjunto de operaes do TAD (usadas como exemplo)
Cria um n folha, dada a informao a ser armazenada
aloca o n
inicializa os campos, atribuindo NULL aos campos prim e prox
ArvVar* arvv_cria (char c) {
ArvVar *a =(ArvVar *) malloc(sizeof(ArvVar));
a->info = c;
a->prim = NULL;
a->prox = NULL;
return a;
}
12
Insere uma nova subrvore como filha de um dado n
insere uma nova sub-rvore como filha de um dado n,
sempre no incio da lista, por simplicidade
void arvv_insere (ArvVar* a, ArvVar* sa) {
sa->prox = a->prim;
a->prim = sa;
}
13
Percorre todos os ns e imprime suas informaes
imprime o contedo dos ns em pr-ordem
void arvv_imprime (ArvVar* a){
ArvVar* p;
printf("<%c\n",a->info);
for (p=a->prim; p!=NULL; p=p->prox)
arvv_imprime(p); /* imprime filhas */
printf(">");
}
14
Verifica a ocorrncia de uma dada informao na rvore
int arvv_pertence (ArvVar* a, char c) {
ArvVar* p;
if (a->info==c)
return 1;
else {
for (p=a->prim; p!=NULL; p=p->prox) {
if (arvv_pertence(p, c))
return 1;
}
}
return 0;
}
15
Libera toda a memria alocada pela rvore
libera a memria alocada pela rvore
libera as sub-rvores antes de liberar o espao associado a
um n (libera em ps-ordem)
void arvv_libera (ArvVar* a) {

ArvVar* p = a->prim;
while (p!=NULL) {
ArvVar* t = p->prox;
arvv_libera(p);
p = t;
}
free(a);
}
16
Altura
nvel e altura
(definidos de forma semelhante a rvores binrias)
exemplo:
h=3
a
17
Altura
Funo arvv_altura
maior altura entre as sub-rvores, acrescido de uma
unidade
caso o n raiz no tenha filhos, a altura da rvore deve ser
0
int arvv_altura (ArvVar* a) {
int hmax = -1; /* -1 para arv. sem filhos */
ArvVar* p;
int h = arvv_altura(p);
if (h > hmax)
hmax = h;
}
return hmax + 1;
}
18
Exerccio
Implemente uma funo que retorne a quantidade de
folhas de uma rvore com nmero varivel de filhos.
Essa funo deve obedecer ao prottipo:
int folhas (ArvVar* a);
Implemente uma funo que compare se duas rvores

so iguais (apenas em estrutura). Essa funo deve
obedecer ao prottipo:
int igual (ArvVar* a, ArvVar* b);
19
Respostas
int folhas (ArvVar* a) {
ArvVar* p;
int n = 0;
if (a->prim == NULL)
return 1;
n = n + folhas(p);
}
return n;
}
20
Respostas
(cont.)
int igual (ArvVar* a, ArvVar* b) {

ArvVar* p;
ArvVar* q;
if (a == NULL && b == NULL)
return 1;
for (p=a->prim, q=b->prim; p!=NULL && q!=NULL;
p=p->prox, q=q->prox) {
if (!igual(p,q))
return 0;
};
return 1;
}
21
Exerccios
Considerando as seguintes declaraes de uma rvore
genrica:
struct arvvar {
int info;
struct arvvar* prim;
struct arvvar* prox;
};
implemente uma funo que, dada uma rvore, retorne

a quantidade de ns que guardam valores maiores que
um determinado valor x (tambm passado como
parmetro). Essa funo deve obedecer o prottipo:
int maiores (ArvVar* a, int x)
22
Exerccios
Considerando as seguintes declaraes de uma rvore
genrica
struct arvvar {
int info;
struct arvvar* prim;
struct arvvar* prox;
};
implemente uma funo que, dada uma rvore, retorne

a quantidade de ns que possuem apenas um filho. Essa
funo deve obedecer o prottipo:
int um_filho (ArvVar* a);
23

Tipos de Árvores

Enviado por

Direitos autorais:

Formatos disponíveis

Tipos de Árvores

Enviado por

Dados do documento

Descrição original:

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Tipos de Árvores

Enviado por

Direitos autorais:

Formatos disponíveis

Estruturas de Dados

Slides baseados no material da PUC-Rio,

rvore com Nmero Varivel de Filhos

A rvore exemplo seria representado por

Funo para imprimir

Note que no h uma maneira sistemtica para acessar

Uma outra representao possvel

ponteiro para a prxima sub-rvore irmo

N folha definido como n com zero subrvores

Funes no consideram o caso de rvore vazias (prcondio)

Exemplo de TADArvVar (TadArvVar.h)

Cria um n folha, dada a informao a ser armazenada

Insere uma nova subrvore como filha de um dado n

Percorre todos os ns e imprime suas informaes

Verifica a ocorrncia de uma dada informao na rvore

Libera toda a memria alocada pela rvore

void arvv_libera (ArvVar* a) {

Implemente uma funo que compare se duas rvores

int igual (ArvVar* a, ArvVar* b) {

implemente uma funo que, dada uma rvore, retorne

implemente uma funo que, dada uma rvore, retorne

Você também pode gostar