• Implemente inclusão e percurso em-ordem em árvores binárias (sem balanceamento).
• Descubra o que são ponteiros para funções em C. Em seguida, refaça as funções para percorrer a árvore em-ordem, pré-ordem e pós-ordem, de forma que elas aceitem uma função que será chamada em cada nó. Faça seu programa ler do teclado números, incluir em uma árvore, e depois percorrer:
  • Mostrando os números
  • Multiplicando o i-ésimo número por (1 quando i é par, ou -1 quando i é ímpar). Mostre a soma dos produtos no final.
• Considere uma árvore representada usando o esquema filho-esquerdo/irmão-à-direita. Como você imagina diferentes maneiras de percorrê-la? Há analogos aos percursos pré-ordem, em-ordem e pós-ordem em árvores binarias? Mostre todos os algoritmos que mencionar.
• Veja a implementação de inserção e remoção em árvore AVL feita em Lisp nesta página. Este algoritmo é puramente funcional.
  • Aprenda um mínimo de Common Lisp para entender a implementação. Você pode usar os seguintes textos:
    • Practical Common Lisp de Peter Seibel
    • Um vídeo de Peter Seibel sobre Lisp (palestra no Google). Aliás, procurem mais vídeos de Google tech talks -- são muito bons!
    • Common Lisp: A Gentle Introduction to Symbolic Computation de David Touretzky
    • Common Lisp: an interactive approach de Stuart Shapiro
    • Common Lisp: the language, um manual de referência
    • Common Lisp Quick Reference, uma referência rápida
    • Common Lisp: Intro, Resources & FAQ
  • Descubra o que é "puramente funcional" e "efeito colateral" neste contexto, e descreva. Diga porque este algoritmo é puramente funcional.
  • Compare esta implementação com as implementações imperativas do livro (Szwarcfiter&markenzon). Implemente ambas em C. Não precisa usar listas para representar a árvore; basta usar a idéia de algoritmo puramente funcional em uma implementação, e usar efeitos colaterais na outra. Teste sua implementação.
  • Faça um benchmark, medindo o tempo que cada implementação demora para inserir e remover dados em ordem aleatória (desta vez, meça o tempo, e não o número de operações, como no exercício de ordenação). Use o gprof para fazer profiling das funções, inclusive funções que alocam memória. Comente o resultado.

A linguagem Common Lisp pode ser usada para programação puramente funcional, como nesse exemplo, ou de outras formas: programação funcional não-pura, programaçõa imperativa, e orientada a objetos. Se quiser saber mais sobre Lisp -- uma das linguagens mais flexíveis já inventadas -- veja o "guia altamente tendencioso" de Pascal Constanza; a "lista de features" compilada por Abhishek Reddy; o "survey de implementações atuais" de Dan Weinreb; e fialmente, o texto um tanto exagerado de Paul Graham.