12.LabII.TADArvoreBinaria-Exercicios

Prévia do material em texto

Laboratório de Programação II
Departamento de Ciência da Computação
UFJF
Aula de hoje
•TAD Árvore Binária
–Percursos
–Exercícios
Árvore Binária
class No
{
private:
No* esq; // ponteiro para o filho a esquerda
int info; // informação do No (int)
No* dir; // ponteiro para o filho a direita
public:
No() {};
~No() {};
void atribEsq(No *p) { esq = p; };
void atribInfo(int val) { info = val; };
void atribDir(No *p) { dir = p; };
No* consultaEsq() { return esq; };
int consultaInfo() { return info; }
No* consultaDir() { return dir; };
};
Árvore Binária
class ArvBin
{
private:
No* raiz; // ponteiro para o No raiz da árvore
bool AuxBusca(No *p, int C);
No* AuxLibera(No *p);
public:
ArvBin();
~ArvBin();
int ConsultaRaiz();
void Cria(int C, ArvBin *sae, ArvBin *sad);
bool Vazia();
bool Busca(int C);
};
Árvore Binária
int ArvBin::ContaNos()
{
return AuxContaNos(raiz);
}
int ArvBin::AuxContaNos(No *p)
{
if (p == NULL) return 0;
else
{
return 1 + AuxContaNos(p->consultaEsq())
+ AuxContaNos(p->consultaDir());
}
}
Realiza percurso “pré-ordem”
Árvore Binária
•Percursos em árvores binárias
–Pré-ordem:
•Raiz, Esq, Dir
–Em ordem:
•Esq, Raiz, Dir
–Pós-ordem:
•Esq, Dir, Raiz
Árvore Binária
int ArvBin::AuxContaNos(No *p)
{
if (p == NULL) return 0;
else
return 1 + AuxContaNos(p->consultaEsq()) + AuxContaNos(p->consultaDir());
}
int ArvBin::AuxContaNos(No *p)
{
if (p == NULL) return 0;
else
return AuxContaNos(p->consultaEsq()) + 1 + AuxContaNos(p->consultaDir());
}
int ArvBin::AuxContaNos(No *p)
{
if (p == NULL) return 0;
else
return AuxContaNos(p->consultaEsq()) + AuxContaNos(p->consultaDir()) + 1;
}
•Como calcular a média dos valores da
árvore?
•O problema que essa implementação
percorre a árvore 2 vezes, uma vez para
somar, e uma vez para contar o total de nós.
Árvore Binária
int ArvBin::MediaNos()
{
if(!Vazia())
return (float) SomaNos()/ContaNos();
}
Exercício
1. Implementar uma operação para calcular a 
média percorrendo a árvore apenas uma vez. 
Dica:
class ArvBin {
private:
...
void AuxMediaNos(No *p, float *soma, int *cont);
...
public:
...
float MediaNos();
...
};
Árvore Binária
•Nível
0
1
2
3
20
10
30
25 33
8 15
6 9 14 18
Exercício
2. Implementar uma operação para imprimir
todos os valores de um dado nível k da árvore
binária.
Dica:
class ArvBin {
private:
...
void AuxImprimeNosNivel(No *p, int nivAtual, int k);
...
public:
...
void ImprimeNosNivel(int k);
...
};
Exercício
3. Implementar uma operação para somar o
valor de todos os nós de um dado nível k da
árvore binária.
Dica:
class ArvBin {
private:
...
void AuxSomaNosNivel(No *p, int *soma, int n, int k);
...
public:
...
int SomaNosNivel(int k);
...
};
Árvore Binária
•Percurso em largura
–Visita todos os nós da árvore ao visitar todos os
nós de um mesmo nível antes de seguir para o
próximo nível
Saída
20, 10, 30, 8, 15, 25, 33, 6, 9, 14, 18
20
10
30
25 33
8 15
6 9 14 18
Árvore Binária
•Percurso em largura
–Uma forma de implementar é usando uma Fila
–Descrição
•Cria fila vazia
•Enfileira raiz
•Enquanto a fila não estiver vazia
–Desenfileira um nó
–Visita o nó
–Enfileira filho da esquerda
–Enfileira filho da direita
Árvore Binária
•Percurso em largura
–Uma forma de implementar é usando uma Fila
Passo 1
Fila
“Vazia”
Passo 2
Fila
Início (Fim)
20
20
10
30
25 33
8 15
6 9 14 18
Árvore Binária
•Percurso em largura
–Uma forma de implementar é usando uma Fila
Fila
20
Saída
20
Fila
10, 30
20
10
30
25 33
8 15
6 9 14 18
Árvore Binária
•Percurso em largura
–Uma forma de implementar é usando uma Fila
20
10
30
25 33
8 15
6 9 14 18
Saída
20, 10
Fila
30, 8, 15
Fila
10, 30
Árvore Binária
•Percurso em largura
–Uma forma de implementar é usando uma Fila
Saída
20, 10, 30, ...........
Fila
8, 15, 25, 33
Fila
30, 8, 15
20
10
30
25 33
8 15
6 9 14 18
Exercício
4. Implementar uma operação para imprimir a
árvore binária utilizando o percurso em largura.
Obs1: Utilize o TAD Fila fornecido. Este TAD armazena
uma fila de ponteiros para nós da árvore binária.
Obs2: A implementação não é recursiva.
Dica:
class ArvBin {
public:
...
void ImprimeLargura();
...
};