Istruzioni
Cambia il genitore di un albero su un nodo selezionato.
Un albero è un tipo particolare di grafo in cui tutti i nodi sono collegati ma non ci sono cicli.
Questo significa che, per qualsiasi coppia di nodi, esiste esattamente un percorso per andare da un nodo all'altro.
Questo esercizio consiste nel riorientare un albero per vedere le cose da un punto di vista diverso.
Per esempio, gli alberi genealogici sono di solito presentati dal punto di vista dell'antenato:
+------0------+
| | |
+-1-+ +-2-+ +-3-+
| | | | | |
4 5 6 7 8 9
Ma in un albero non c'è una direzione intrinseca.
Le stesse informazioni si possono presentare dal punto di vista di qualsiasi altro nodo dell'albero, portandolo fino alla radice e trascinando con sé le sue relazioni.
Quindi lo stesso albero visto dal nodo 6 apparirebbe così:
6
|
+-----2-----+
| |
7 +-----0-----+
| |
+-1-+ +-3-+
| | | |
4 5 8 9
Così possiamo descrivere più semplicemente i percorsi tra due nodi.
Per esempio, il percorso 6-9 (che nel primo albero sale fino alla radice e poi scende fino a un nodo foglia diverso) si può vedere come il percorso 6-2-0-3-9.
Questo esercizio consiste nel prendere un albero in input e riorientarlo dal punto di vista di uno dei nodi.
Note sull'implementazione
Il programma di test crea gli alberi applicando ripetutamente la funzione variadica New.
Per esempio, l'istruzione
tree := New("a",New("b"),New("c",New("d")))
costruisce il seguente albero:
"a"
|
-------
| |
"b" "c"
|
"d"
Puoi assumere che negli alberi di test non ci siano valori duplicati.
Il programma di test userà i metodi Value e Children per scomporre gli alberi.
La costruzione e la scomposizione di base degli alberi deve funzionare prima di iniziare la parte interessante dell'esercizio, quindi viene testata separatamente nei primi tre test.
I metodi FromPov e PathTo sono la parte interessante dell'esercizio.
Il metodo FromPov accetta un argomento di tipo stringa, from, che specifica un nodo dell'albero tramite il suo valore.
Deve restituire un albero con il valore from nella radice.
Puoi modificare l'albero originale e restituirlo, oppure creare un nuovo albero e restituire quello.
Se restituisci un nuovo albero, sei libero di consumare o distruggere l'albero originale.
Ovviamente, è preferibile lasciarlo invariato.
Il metodo PathTo accetta due argomenti di tipo stringa, from e to, che specificano due nodi dell'albero tramite i loro valori.
Deve restituire il percorso più breve nell'albero dal primo al secondo nodo.
