Punto di vista

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 di implementazione

L'oggetto Tree ha due attributi:

• String label
• List<Tree> children

Il programma di test crea gli alberi applicando ripetutamente la funzione di costruzione Tree.of. Per esempio, l'istruzione

Tree tree = Tree.of("a", List.of(Tree.of("b"), Tree.of("c", List.of(Tree.of("d")))));

costruisce il seguente albero:

      "a"
       |
    -------
    |     |
   "b"   "c"
          |
         "d"

Puoi assumere che negli alberi di test non ci siano valori duplicati.

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. Dovrebbe 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. Naturalmente, è bello lasciarlo invariato.

Il metodo PathTo accetta due argomenti di tipo stringa, from e to, che specificano due nodi dell'albero tramite i loro valori. Dovrebbe restituire il percorso più breve nell'albero dal primo al secondo nodo.

Messaggi di eccezione

A volte è necessario lanciare un'eccezione. Quando lo fai, dovresti sempre includere un messaggio di errore significativo che indichi qual è la causa dell'errore. Questo rende il tuo codice più leggibile e aiuta notevolmente nel debug.

Questo particolare esercizio richiede che tu usi la parola chiave throw per «lanciare» più UnsupportedOperationException se alla classe Tree() viene passato un albero che non può essere riorientato, oppure se non viene trovato un percorso tra un start node e un end node. I test passeranno solo se lanci exception con throw e ci includi anche un messaggio.

Per lanciare una UnsupportedOperationException con un messaggio, scrivi il messaggio come argomento del tipo exception:

// when a tree cannot be oriented to a new node POV
throw new UnsupportedOperationException("Tree could not be reoriented");

// when a path cannot be found between a start and end node on the tree.
throw new UnsupportedOperationException("No path found");

---

Fonte

Adattamento di un esercizio tratto da 4clojure