Zipper

Instruções

Criar um zipper para uma árvore binária.

Os zippers são uma forma puramente funcional de navegar dentro de uma estrutura de dados e de a manipular. Contêm essencialmente uma estrutura de dados e um ponteiro para dentro dessa estrutura de dados (chamado foco).

Por exemplo, dada uma árvore rosa (em que cada nó contém um valor e uma lista de nós filhos), um zipper pode suportar estas operações:

• from_tree (obtém um zipper a partir de uma árvore rosa; o foco fica no nó raiz)
• to_tree (obtém a árvore rosa a partir do zipper)
• value (obtém o valor do nó em foco)
• prev (move o foco para o filho anterior do mesmo pai; devolve um novo zipper)
• next (move o foco para o filho seguinte do mesmo pai; devolve um novo zipper)
• up (move o foco para o pai; devolve um novo zipper)
• set_value (define o valor do nó em foco; devolve um novo zipper)
• insert_before (insere uma nova subárvore antes do nó em foco; esta passa a ser o prev do nó em foco; devolve um novo zipper)
• insert_after (insere uma nova subárvore depois do nó em foco; esta passa a ser o next do nó em foco; devolve um novo zipper)
• delete (remove o nó em foco e todas as subárvores; o foco passa para o nó next se possível, caso contrário para o nó prev se possível, caso contrário para o nó pai; devolve um novo zipper)