Ficha Nº10: Estruturas de Dados Dinâmicas - Árvores Binárias

Objectivos:

O objectivo principal desta ficha é familiarizar o aluno com a utilização de estruturas de dados dinâmicas, nomeadamente, as árvores binárias.

Exercícios:

Exercício Nº 1: Árvores Binárias Ordenadas de Inteiros

Considere uma lista de inteiros (não se sabe o seu comprimento). Especifique então as seguintes funções e estruturas de dados:

1. Defina os tipos necessários para suportar uma árvore binária ordenada (de procura) de inteiros.
2. Especifique uma função para inserir um valor na árvore.
3. Especifique uma função para listar os valores armazenados (codifique as três funções de listagem possíveis).
4. Especifique uma função para procurar um valor na árvore (como resultado deverá devolver um apontador para o elemento ou NULL caso não o encontre).
5. Especifique uma função para contar os elementos da árvore.
6. Especifique uma função para calcular o maior elemento na árvore.
7. Especifique um programa, usando as funções definidas, que cria uma lista com os múltiplos de 7 entre 0 e 100 e os lista por ordem decrescente e crescente.
8. Especifique uma função que calcula o peso de uma árvore (a sua profundidade).
9. Especifique uma função que dada uma árvore, a lista por níveis.

Exercício Nº 2: Gestão do Login dos Utilizadores de uma Aplicação

Para controlar o acesso a uma aplicação informática, pretende-se manter em memória o conjunto dos pares "Username-Password" de todos os Utilizadores autorizados. Usando uma Árvore Binária de Procura para armazenar essa informação e após definir os tipos de variáveis em C, necessários para suportar essa representação, implemente as seguintes operações na linguagem C:

1. "valida": função booleana que diz se o par "username-password" corresponde a um utilizador válido.
2. "daSenha": função que retorna a password de um dado username.
3. "listaTodos": procedimento que faz uma listagem ordenada alfabeticamente de todos os pares "Username-Password" válidos.
4. "insere": função que recebe um novo par "Username-Password" e a Árvore com o conjunto de utilizadores actuais e devolve uma nova Árvore com o novo par inserido na follha correcta.

Exercício Nº 3: Árvores Binárias para Expressões Aritméticas (+,-,*,/)

1. Defina a estrutura de dados para uma árvore binária que irá armazenar expressões aritméticas, operadores nos nodos intermédios armazenados de acordo com a sua prioridade de cálculo e operandos (números reais) nas folhas.
2. Especifique uma função que dada uma árvore deste tipo lista a expressão na forma: infixa, pré-fixa, pós-fixa.
3. Especifique uma função que dada uma árvore deste tipo calcula o valor da expressão lá armazenada.

Exercício Nº 4: Dicionários

Pretende-se criar um dicionário que associe a cada palavra (termo chave), a sua classificação morfológica, origem, significado e sinónimos. O programa a desenvolver para manipulação do dicionário (suponha que o mesmo foi criado por uma outra aplicação), além de facultar uma consulta eficiente (dada uma palavra retorna toda a informação associada, ou produz uma mensagem de falha, caso não haja nenhuma chave igual à palavra dada), deve permitir listar globalmente toda a informação contida, ordenada alfabeticamente pelos termos-chave, e deve ser capaz de ler e salvar o dicionário em ficheiro binário.

1. Defina a estrutura de dados para armazenar cada entrada (par "termo-chave,informação-associada").
2. Implemente o dicionário num array ordenado de entradas.
3. Implemente o dicionário numa lista ligada dinâmica e ordenada de entradas.
4. Implemente o dicionário usando sub-lista ligadas dinâmica e ordenada de entradas cada lista correspondente a 1 das 26 letras do alfabeto, acessiveis através de um indíce guardado em Árvore Binária de Procura (em alternativa, armazene-o num array).