11.LabII.TADArvoreBinaria

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 em C++.
Árvores
• Árvore:
– Estrutura de dados caracterizada por uma relação
de hierarquia entre os elementos que a
compõem.
• Árvore Binária:
– Caso especial de Árvore;
– Tem como princípio que cada nó da árvore tem
no máximo dois descendentes.
3
Árvore Binária
4
TAD No para uma árvore binária de inteiros
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() {};
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; };
~No() {};
};
Árvore Binária
5
class ArvBin
{
private:
No* raiz; // ponteiro para o No raiz da árvore
bool AuxBusca(No *p, int C);
No* Libera(No *p);
void AuxInOrdem(No *p);
public:
ArvBin();
int ConsultaRaiz();
// cria novo No como raiz das sub-árvores à esquerda
// (sae) e à direita (sad)
void Cria(int C, ArvBin *sae, ArvBin *sad);
bool Vazia(); // verifica se a árvore está vazia
bool Busca(int C);
void InOrdem();
~ArvBin();
};
TAD ArvBin (árvore binária de inteiros)
Árvore Binária
6
 MI do TAD ArvBin:
 Construtor:
ArvBin::ArvBin()
{
raiz = NULL;
}
raiz
Cria árvore binária vazia
Árvore Binária
7
int ArvBin::ConsultaRaiz()
{
if (raiz != NULL)
return raiz-> consultaInfo();
else
{
cout << "Árvore vazia!" << endl;
exit(1);
}
}
 MI do TAD ArvBin:
 Operação ConsultaRaiz:
Árvore Binária
8
 MI do TAD ArvBin:
 Operação Cria:
void ArvBin::Cria(int C, ArvBin *sae, ArvBin *sad)
{
No *p = new No();
p-> atribInfo(C);
p->atribEsq(sae->raiz);
p->atribDir(sad->raiz);
raiz = p;
}
Árvore Binária
9
 MI do TAD ArvBin:
 Operação Vazia:
bool ArvBin::Vazia()
{
if (raiz == NULL)
return true;
else
return false;
}
Árvore Binária
10
 MI do TAD ArvBin:
 Operação Busca:
bool ArvBin::Busca(int C)
{
return AuxBusca(raiz, C);
}
Árvore Binária
11
 MI do TAD ArvBin:
 Operação AuxBusca:
bool ArvBin::AuxBusca(No *p, int C)
{
if (p == NULL)
return false;
else if (p->consultaInfo() == C)
return true;
else if (AuxBusca(p->consultaEsq(),C))
return true;
else
return AuxBusca(p->consultaDir(),C);
}
Árvore Binária
12
 MI do TAD ArvBin:
Destrutor:
ArvBin::~ArvBin()
{
raiz = Libera(raiz);
}
Árvore Binária
13
 MI do TAD ArvBin:
 Operação Libera:
No* ArvBin::Libera(No *p)
{
if (p != NULL)
{
p->atribEsq(Libera(p->consultaEsq()));
p->atribDir(Libera(p->consultaDir()));
delete p;
p = NULL;
}
return NULL;
}
Árvore Binária
14
 MI do TAD ArvBin:
 Operação InOrdem:
void ArvBin::InOrdem()
{
AuxInOrdem(raiz);
}
Árvore Binária
15
 MI do TAD ArvBin:
 Operação AuxInOrdem:
void ArvBin::AuxInOrdem(No *p)
{
if (p != NULL)
{
AuxInOrdem(p->consultaEsq());
cout << p->consultaInfo() << " ";
AuxInOrdem(p->consultaDir());
}
}
Árvore Binária
• Ex.: Desenvolver um PA para criar a seguinte 
árvore binária:
16
20
10
30
25 33
8 -5
6 9 18 14
Árvore Binária
int main()
{
//constrói 5 árvores binárias vazias
ArvBin *Arv = new ArvBin();
ArvBin *a1 = new ArvBin();
ArvBin *a2 = new ArvBin();
ArvBin *a3 = new ArvBin();
ArvBin *vazia = new ArvBin();
//as 2 arvores possuem raízes 6 e 9 e sae e sad vazias
a1->Cria(6, vazia, vazia);
a2->Cria(9 ,vazia, vazia);
//raiz de Arv tem valor 8 e sae a1 e sad a2
Arv->Cria(8, a1, a2);
a1->Cria(18, vazia, vazia);
a2->Cria(14, vazia, vazia);
a3->Cria(-5, a1, a2);
Árvore Binária
//raiz de Arv tem valor 10 e sae Arv e sad a3
Arv->Cria(10, Arv, a3);
a1->Cria(25, vazia, vazia);
a2->Cria(33, vazia, vazia);
a3->Cria(30, a1, a2);
//raiz de Arv tem valor 20 e sae Arv e sad a3
Arv->Cria(20, Arv, a3);
//imprime a árvore construída nos comandos acima
Arv->InOrdem();
delete Arv;
return 0;
}
Exercícios
Considerando o TAD ArvBin, desenvolver as
seguintes operações para:
1. Determinar a altura de uma árvore binária.
2. Contar quantos são os nós de uma árvore
binária.
3. Contar quantas são as folhas de uma árvore
binária.
Exercícios
4. Imprimir todos os valores dos nós de um
dado nível k.
5. Calcular a média dos valores dos nós de um
dado nível k.
6. Calcular a quantidade de valores ímpares
armazenados nos nós folhas de uma árvore
binária.
7. Calcular e retornar a quantidade de valores
ímpares numa árvore binária.
20