Instrucciones
Reasigna el padre de un árbol a un nodo seleccionado.
Un árbol es un tipo especial de grafo en el que todos los nodos están conectados, pero no hay ciclos.
Eso significa que hay exactamente un camino para ir de un nodo a otro para cualquier par de nodos.
Este ejercicio trata de reorientar un árbol para ver las cosas desde otro punto de vista.
Por ejemplo, los árboles genealógicos normalmente se presentan desde la perspectiva del antepasado:
+------0------+
| | |
+-1-+ +-2-+ +-3-+
| | | | | |
4 5 6 7 8 9
Pero no hay una dirección inherente en un árbol.
La misma información se puede presentar desde la perspectiva de cualquier otro nodo del árbol, subiéndolo a la raíz y arrastrando sus relaciones junto con él.
Así, el mismo árbol desde la perspectiva de 6 se vería así:
6
|
+-----2-----+
| |
7 +-----0-----+
| |
+-1-+ +-3-+
| | | |
4 5 8 9
Esto nos permite describir de forma más simple los caminos entre dos nodos.
Por ejemplo, el camino de 6 a 9 (que en el primer árbol sube hasta la raíz y luego baja hasta un nodo hoja diferente) se puede ver que sigue el camino 6-2-0-3-9.
Este ejercicio consiste en tomar un árbol de entrada y reorientarlo desde el punto de vista de uno de sus nodos.
Notas de implementación
El objeto Tree tiene dos atributos:
-
String etiqueta
-
List<Tree> hijos
El programa de prueba crea árboles aplicando repetidamente la función constructora Tree.of. Por ejemplo, la sentencia
Tree tree = Tree.of("a", List.of(Tree.of("b"), Tree.of("c", List.of(Tree.of("d")))));
construye el siguiente árbol:
"a"
|
-------
| |
"b" "c"
|
"d"
Puedes asumir que no habrá valores duplicados en los árboles de prueba.
Los métodos FromPov y PathTo son la parte interesante del ejercicio.
El método FromPov recibe un argumento de tipo string from, que especifica un nodo del árbol mediante su valor. Debe devolver un árbol con el valor from en la raíz. Puedes modificar el árbol original y devolverlo, o crear un árbol nuevo y devolver ese. Si devuelves un árbol nuevo, puedes consumir o destruir el árbol original sin problema. Claro que es mejor dejarlo sin modificar.
El método PathTo recibe dos argumentos de tipo string, from y to, que especifican dos nodos del árbol mediante sus valores. Debe devolver la ruta más corta en el árbol del primer nodo al segundo.
Mensajes de excepción
A veces es necesario lanzar una excepción.
Cuando lo hagas, siempre debes incluir un mensaje de error significativo que indique cuál es el origen del error.
Esto hace que tu código sea más legible y ayuda muchísimo con la depuración.
Este ejercicio en particular requiere que uses la palabra clave throw
para «lanzar» varias UnsupportedOperationException si a la clase Tree() se le pasa un árbol que no se puede reorientar, o si no se puede encontrar una ruta entre un start node y un end node.
Las pruebas solo pasarán si haces throw de la exception e incluyes un mensaje con ella.
Para lanzar una UnsupportedOperationException con un mensaje, escribe el mensaje como argumento 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");
