MAC0122 - Lista 6 - Árvores binárias e árvores binárias de busca

1. Escreva uma função monta-árvore que recebe uma expressão aritmética com operadores +, -, * e / e operandos identificados por uma letra cada um, e devolve uma árvore binária que representa essa expressão, conforme o exemplo mostrado em aula.

2. Escreva uma função calcula que recebe a árvore que você montou no exercício 1 e devolve o valor da expressão nela guardada, supondo que você tem à sua disposição uma rotina valor que, dada uma letra, devolve o valor associado àquela letra na expressão. Quanto tempo sua função consome em função do número de nós da árvore?

3. Escreva uma função posfixa que recebe a árvore que você montou no exercício 1 e imprime a notação posfixa da expressão nela armazenada. Quanto tempo sua função consome em função do número de nós da árvore?

4. Escreva uma versão não-recursiva da função in-ordem.

5. Escreva uma função numNos que recebe uma árvore r e devolve o número de nós que há na árvore r.

6. Escreva uma função recursiva máximo que recebe uma árvore r não-vazia e devolve um apontador para o nó com conteúdo máximo em r.

7. Escreva uma função espelha que recebe uma árvore r e devolve a árvore espelhada, composta pelos mesmo nós que r.

8. Escreva uma função copia que recebe uma árvore r e devolve uma cópia da árvore r.

9. Escreva uma função libera que recebe uma árvore r e libera todos os nós da árvore r.

10. Escreva uma função predecessor que recebe o apontador q para um nó de um ABB e devolve um apontador para o nó que precede q na árvore (e NULL caso q seja o mínimo da ABB).

11. Escreva uma função nível que recebe uma ABB r e um elemento x que aparece na árvore r, e devolve o nível do nó que contém x em r. Escreva uma versão recursiva e uma não-recursiva desta função. Quanto tempo cada uma das versões consome?

12. Qual é a diferença entre a propriedade de uma árvore binária de busca (ABB) e um heap? Dado um heap com n elementos, é possível imprimir os valores nele contidos em ordem crescente em tempo O(n)? Explique como ou porque não. Dada uma ABB com n elementos, é possível imprimir os valores nela contidos em ordem crescente em tempo O(n)? Explique como ou porque não.

13. O Prof. Xis acha que descobriu uma propriedade muito interessante de ABBs. Suponha que a busca por um elemento x em uma ABB termina em uma folha. Considere três conjuntos: o conjunto A com os valores da árvore à esquerda do caminho percorrido na busca, o conjunto B com os valores deste caminho, e o conjunto C, com os valores à direita deste caminho. O Prof. Xis afirma que quaisquer três valores a em A, b em B e c em C satisfazem a <= b <= c. Dê um contra-exemplo o menor possível para a afirmação do Prof. Xis.

14. Podemos ordenar um conjunto de n números primeiramente construindo uma ABB contendo estes números e então imprimindo o conteúdo da árvore em ordem crescente. Qual é o tempo de execução para este algoritmo de ordenação no pior e no melhor caso? Explique sua resposta.

15. Escreva a função remoção, que recebe o apontador p para um nó de uma ABB e remove o conteúdo do nó apontado por p da ABB, deixando-a uma ABB após a operação.