Descomprima o ficheiro
lab10.zip, fornecido abaixo, que contém quatro ficheiros:
BST.h,
BST.c,
Item.h,
client.c e
Makefile. Os ficheiros
BST.h e
BST.c implementam um ADT árvore binária. O ficheiro
Item.h contém as definições habituais, utilizadas pelo ADT. O ficheiro
client.c utiliza o ADT, inserindo um conjunto de números inteiros na árvore e pesquisando-os posteriormente. Analize o conteúdo dos ficheiros.
Modifique o ficheiro
client.c, por forma a que imprima a altura da árvore. Verifique que a ordem de inserção dos elementos conduz à degeneração da árvore numa lista. Utilizando o comando
time determine o tempo de execução do programa. Nota: existe uma função no ADT que devolve a altura da árvore.
No ficheiro
BST.c retire os comentários ao código que introduz aleatoriedade na inserção de elementos. Compare a altura da árvore e o tempo execução obtidos com os do caso anterior.
Volte a comentar o código que introduz aleatoriedade na inserção de elementos. Modifique o ficheiro
client.c por forma a que a árvore seja equilibrada antes do início da procura. Compare a altura da árvore e o tempo execução obtidos com os dos casos anteriores. Que conclusóes pode tirar ? Nota: existe uma função no ADT que equilibra a árvore.
Modifique o ficheiro
client.c por forma a que os números guardados na árvore sejam impressos por ordem crescente. Deverá invocar a função
STsort() para o efeito.
Altere apenas uma linha do ficheiro
Item.h por forma a que o programa imprima os números por ordem crescente dos respectivos restos da divisão inteira por 10.
Altere apenas uma função do ficheiro
BST.c, por forma a que os números sejam impressos por ordem descrescente.
Implemente uma função
BSTcleanup(), que liberta a memória ocupada pelas estrutura de dados. Invoque a função no final da execução do programa.
