Instruções
Reparentar uma árvore num nó selecionado.
Uma árvore é um tipo especial de grafo em que todos os nós estão ligados, mas não existem ciclos.
Isto significa que existe exatamente um caminho para ir de um nó a outro, para qualquer par de nós.
Este exercício consiste em receber uma árvore e reorientá-la para ver as coisas de outro ponto de vista.
Por exemplo, as árvores genealógicas são normalmente apresentadas na perspetiva do antepassado:
+------0------+
| | |
+-1-+ +-2-+ +-3-+
| | | | | |
4 5 6 7 8 9
Mas uma árvore não tem uma direção inerente.
A mesma informação pode ser apresentada na perspetiva de qualquer outro nó da árvore, puxando-o até à raiz e arrastando consigo as suas relações.
Por isso, a mesma árvore na perspetiva do 6 ficaria assim:
6
|
+-----2-----+
| |
7 +-----0-----+
| |
+-1-+ +-3-+
| | | |
4 5 8 9
Assim, podemos descrever de forma mais simples os caminhos entre dois nós.
Por exemplo, o caminho de 6 a 9 (que na primeira árvore sobe até à raiz e depois desce até um nó folha diferente) segue o caminho 6-2-0-3-9.
Este exercício consiste em receber uma árvore e reorientá-la do ponto de vista de um dos nós.
Notas de implementação
O programa de teste cria árvores através da aplicação repetida da função variádica New.
Por exemplo, a instrução
tree := New("a",New("b"),New("c",New("d")))
constrói a seguinte árvore:
"a"
|
-------
| |
"b" "c"
|
"d"
Podes assumir que não haverá valores duplicados nas árvores de teste.
Os métodos Value e Children serão usados pelo programa de teste para desconstruir as árvores.
A construção e desconstrução básica da árvore têm de estar a funcionar antes de começares a parte interessante do exercício, por isso são testadas separadamente nos primeiros três testes.
Os métodos FromPov e PathTo são a parte interessante do exercício.
O método FromPov recebe um argumento string from, que especifica um nó da árvore através do seu valor.
Deve devolver uma árvore com o valor from na raiz.
Podes modificar a árvore original e devolvê-la, ou criar uma nova árvore e devolver essa.
Se devolveres uma nova árvore, és livre de consumir ou destruir a árvore original.
Claro que é agradável deixá-la inalterada.
O método PathTo recebe dois argumentos string from e to, que especificam dois nós da árvore através dos seus valores.
Deve devolver o caminho mais curto na árvore do primeiro para o segundo nó.
