INF1010 - Árvores Binárias de Busca

Utilização do Ambiente Linux

Abra um terminal onde você irá interagir com o sistema através de linha de comando.
Na interação por linha de comando, existe o conceito de diretório corrente, que é a pasta de arquivos onde você está "posicionado''. Escreva pwd e dê enter para descobrir quem é o diretório corrente. Use o comando ls para listar o conteúdo desse diretório.
Crie um diretório para seus programas de inf1010. Use o comando mkdir inf1010 para isso. Em seguida, dê cd inf1010 e volte a usar o comando pwd para verificar qual é, agora, o diretório corrente.
Para criar um programa, abra um editor de texto (por exemplo, gedit), escreva seu programa, e salve o programa em um arquivo, por exemplo, ex1.c, na pasta inf1010. Volte ao terminal e execute o comando abaixo:
```
gcc -Wall -o ex1 ex1.c
```
Para executar o resultado, use:
```
./ex1
```
Obs: A opção -Wall diz ao gcc para gerar warnings (avisos) e o argumento -o o instrui a colocar o resultado da compilação, o programa executável, no arquivo cujo nome vem a seguir, no caso: ex1
Você irá usar isso durante o curso inteiro, então por favor tente entender essa linha de comando.
Para criar um programa que tem mais de um módulo, basta escrever:
```
gcc -Wall -o meuprograma modulo1.c modulo2.c
```

Árvores Binárias de Busca

Usando árvores binárias de busca, vamos completar um módulo com as interface dadas em mapa.h e arvore.h. A primeira é a interface do tipo abstrato mapa, e a segunda uma interface para a estrutura de dados árvore. Um esboço dessa implementação está em mapa.c. Repare que, neste caso, a implementação oferece as duas interfaces, ou seja, além de oferecer as operações comuns de mapa, algumas outras operações, que assumem que o mapa é implementado como uma árvore binária, são oferecidas para os "usuários" da interface arvore.h.

Note que trocamos os dados indicados em sala de aula (onde cada nó da árvore "apontava" para um bloco de dados) por um simples inteiro. O objetivo aqui é só simplificar o tratamento desses dados em nosso exercício. A operação busca agora retorna um int. Para indicar que o item não foi encontrado, estamos retornando o valor INT_MIN (para definir essa constante, precisamos incluir o arquivo limits.h).

Use o arquivo teste.c como base para seus testes. Este programa teste cria 2 mapas (implementados como árvores binárias de busca), utilizando a função cria_raiz, da interface arvore.h. Essa função já está implementada em mapa.c. Em seguida, ele mostra a estrutura das duas árvores utilizando a função mostra, também já implementada.
Depois, o programa teste chama todas as funções que você deve implementar, verificando se o resultado está correto. Como essas funções não estão corretamente implementadas, o resultado não estará correto! Antes de começar a implementar as funções pedidas abaixo, observe o código implementado em mapa.c e tente entendê-lo! Note que, além das funções que você implementará, algumas funções da interface mapa ainda não estão prontas (mais tarde nós as implementaremos).
Desenhe no papel o que você prevê como árvore resultante para os dois mapas criados, fazendo o chinês da função cria_raiz. Compile e execute o programa formado pelos módulos mapa.c e teste.c e verifique a saída.
Implemente a função num_nos da interface arvore.h. Ela deve retornar o número de nós de uma árvore. Tente pensar "recursivamente", lembrando que toda árvore binária ou é vazia ou tem uma raiz e duas subárvores. Então, se você conhece o número de nós das subárvores, você sabe dizer o número de nós de uma árvore... Use o programa teste para testar sua função!
Implemente a função maior_chave, que retorna a maior chave armazenada em uma árvore. Sua função deve levar em consideração a ordenação da árvore binária de busca, ou seja, não percorra uma subárvore se isto não for necessário! Caso a árvore seja vazia, retorne INT_MIN. Teste a função, verificando se o resultado está correto.
Implemente a função num_maiores_que, da interface arvore.h. Essa função recebe uma árvore binária de busca, e um valor inteiro e retorna o número de nós cujas chaves são maiores que o valor dado. Novamente, a sua função deve levar em consideração a ordenação da árvore binária de busca (isto é, não percorra uma subárvore se isto não for necessário ). Teste sua função e verifique se o resultado está correto.
(extra) Tente pensar em como deve ser feita a inserção de um nó em uma árvore binária de busca. Desenhe no papel uma árvore (pode ser uma das árvores usadas no programa de teste), e suponha um novo valor de chave a ser inserido nessa árvore. Usando o seu desenho para percorrer a árvore, como você descobre o local onde o nó correspondente a essa chave deve ser inserido? Experimente valores diferentes para chave. (Dica: a inserção não é muito diferente de uma busca, porque você está "buscando" o local onde o nó deve ser inserido, respeitando a ordenação representada na árvore).
Você consegue agora implementar a função insere definida na interface de Mapa? Para criar o novo nó, você pode usar a função auxiliar cria_no, que já está no arquivo mapa.c.
Lembre-se que, ao percorrer a árvore, se você encontra uma (sub)árvore vazia, o novo nó será a nova raiz dessa (sub)árvore...
Para testar sua função, aumente o programa de teste, colocando alguns testes de inserção, mostrando depois de cada inserção como ficou a árvore (usando, por exemplo, a função mostra).

Entrega do Laboratório

Faça upload dos seus arquivos mapa.c e teste.c no EAD. Indique na área de texto, que funções você implementou, e se o resultado verificado para cada uma está correto ou não.

Lembre-se de fazer a entrega mesmo que não tenha chegado ao final do exercício.