Coloque também em seu projeto o arquivo
testaarvore.c,
que contém uma função main que usa as
funções deste módulo.
As funções que você deverá implementar são por enquanto
apenas "esqueletos" em arvore.c e, por isso,
o programa de teste exibirá resultados "errados" enquanto
você não implementá-las...
Dê uma olhada nas funções de arvore.c.
Algumas delas já vimos em sala: arvCriaVazia, arvCria, arvVazia,
arvLibera.
Repare que a função arvImprime recebe um
parâmetro nivel: ele é usado para podermos imprimir
a árvore "reproduzindo" sua estrutura hierárquica.
Antes de mostrar a informação de cada nó,
colocamos "tabs" que correspondem ao "nível hierárquico"
do nó: a raiz tem nível 0, seus filhos tem nível 1,
e assim por diante.
Crie a aplicação e a execute, verificando como as duas
árvores criadas pela main são exibidas!
Atenção: todas as funções que você vai implementar pertencem ao no módulo arvore.c!
Implemente em arvore.c a função
arvInternos, que
recebe uma árvore binária e retorna o número de nós
internos dessa árvore (isto é,
o número de nós que não são folhas).
Essa função tem o seguinte protótipo:
int arvInternos(NoArvore *a);
Teste o programa, verificando se o resultado exibido está correto!
Implemente agora em arvore.c a função
arvMaior, que
recebe uma árvore binária e retorna o maior valor inteiro
armazenado na árvore.
Se a árvore está vazia, a função deve retornar -1.
Assuma que todos os valores armazenados são inteiros não negativos (ou seja, maiores ou iguais a zero).
Essa função tem o seguinte protótipo:
int arvMaior(NoArvore *a);
Teste o programa, verificando se o resultado exibido está correto!
Implemente agora em arvore.c a função arvIguais,
que compara se duas árvores binárias são iguais.
A função deve retornar 1 se as árvores são iguais e 0 caso contrário.
Atenção: árvores iguais devem ter a mesma estrutura hierárquica
e armazenar a mesma informação nos nós de mesma posição nas duas árvores.
Essa função tem o seguinte protótipo:
int *arvIgual(NoArvore *a1, NoArvore *a2);
Definimos a altura de uma árvore como sendo o comprimento do caminho mais longo da raiz até uma das folhas. Por exemplo, o caminho da raiz até seus filhos é 1, da raiz até os filhos de seus filhos é 2, e assim por diante...
Nas nossas duas árvores criadas pela main, a primeira
árvore tem altura 2 (o comprimento de todos os caminhos da raiz
até as folhas é 2) e a segunda árvore tem altura 3
(o comprimento do caminho da raiz até o nó com
informação 10 é 3, e este é o maior caminho).
Implemente agora em arvore.c a
função arvalturaMaior,
que recebe uma árvore binária e um valor inteiro, e testa
se a altura da árvore é maior que este valor.
A função deve retornar 1 se a altura é maior,
e 0 caso contrário.
Seu protótipo é
int arvAlturaMaior(NoArvore *a, int altura);
Dica: Observe, novamente, a função
arvImprime: nas chamadas (recursivas) para as subárvores,
ela incrementa o valor do parâmetro nivel.
Você pode usar uma estratégia semelhante,
"diminuindo" o tamanho da altura a ser testada...
Teste o programa, verificando se o resultado exibido está correto!