9
GUIÃO DAS AULAS PRÁTICAS DE ALGORITMOS E COMPLEXIDADE
AULA 9
O Tipo Abstracto de Dados Árvore Binária de Pesquisa (ABP) é constituído pelo ficheiro de interface
abp.h e pelo ficheiro de implementação abp.c e implementa a manipulação de árvores binárias de
pesquisa, com capacidade para armazenar números inteiros. O TAD tem capacidade de múltipla
instanciação e usa um controlo centralizado de erros. Para testar o TAD é fornecido o programa tabp.c
e a makefile mkabp. Comece por testar convenientemente toda funcionalidade do TAD, usando para
esse efeito os ficheiros de árvores disponibilizados. Também é fornecido o programa irabp.c que
simula a inserção e a remoção de elementos na árvore, fazendo a sua visualização hierárquica na
horizontal, após cada operação. Simule o programa para as sequências de elementos dos ficheiros.
Acrescente ao Tipo Abstracto de Dados Árvore Binária de Pesquisa a seguinte funcionalidade:
 Uma função iterativa para obter um ponteiro para o nó do menor elemento armazenado na árvore.
A função deve ter o seguinte protótipo:
PtABP ABPMinNode (PtABP pabp);
 Uma função recursiva para obter um ponteiro para o nó do maior elemento armazenado na árvore.
A função deve ter o seguinte protótipo:
PtABP ABPMaxNode (PtABP pabp);
 Uma função para obter o elemento armazenado na árvore, dado um ponteiro para o seu nó. A
função deve ter o seguinte protótipo:
int ABPElement (PtABP pnode);
 Uma função recursiva para determinar a soma dos elementos armazenados na árvore. A função
deve ter o seguinte protótipo:
int ABPTotalSum (PtABP pabp);
 Uma função iterativa para determinar o número de elementos múltiplos de 7 armazenados na
árvore. A função deve ter o seguinte protótipo:
unsigned int ABPMult7Count (PtABP pabp);
 Uma função recursiva para determinar o número de elementos pares armazenados na árvore. A
função deve ter o seguinte protótipo:
unsigned int ABPEvenCount (PtABP pabp);
 Uma função iterativa para determinar a soma dos elementos ímpares armazenados na árvore. A
função deve ter o seguinte protótipo:
int ABPOddSum (PtABP pabp);
 Uma função para determinar a soma dos elementos armazenados na árvore, com número de ordem
ímpar. Ou seja, a soma do primeiro, terceiro, quinto, sétimo, etc. menores números inteiros
armazenados na árvore. A função deve ter o seguinte protótipo:
int ABPOddOrderSum (PtABP pabp);
 Uma função para determinar se duas árvores são iguais. Entenda-se por árvores iguais, duas árvores
que armazenam os mesmos elementos, independentemente da sua organização interna. A função
deve ter o seguinte protótipo:
int ABPEquals (PtABP pabp1, PtABP pabp2);
10
GUIÃO DAS AULAS PRÁTICAS DE ALGORITMOS E COMPLEXIDADE
Escreva um programa, chamado por exemplo testeabp.c que permita testar estas operações. O
programa constrói uma árvore binária de pesquisa a partir de um ficheiro, cujo nome é passado como
argumento na linha de comando e depois apresenta no monitor, o número de nós e a altura da árvore
criada. De seguida, o programa indica também: o valor do menor elemento armazenado na árvore; o
valor do maior elemento armazenado na árvore; a soma dos elementos da árvore; a contagem dos
números múltiplos de 7 da árvore; o número de números pares da árvore; a soma dos elementos
ímpares da árvore; a soma dos elementos com número de ordem ímpar da árvore. Finalmente, o
programa constrói uma segunda árvore binária de pesquisa, também a partir de um ficheiro, e depois
indica no monitor se as duas árvores são ou não iguais.