POV

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 objeto Tree tem dois atributos:

• String label
• List<Tree> children

O programa de testes cria árvores através da aplicação repetida da função construtora Tree.of. Por exemplo, a instrução

Tree tree = Tree.of("a", List.of(Tree.of("b"), Tree.of("c", List.of(Tree.of("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 FromPov e PathTo são a parte interessante do exercício.

O método FromPov recebe um argumento from do tipo String, 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, podes consumir ou destruir a árvore original à vontade. Claro que é simpático deixá-la sem alterações.

O método PathTo recebe dois argumentos from e to do tipo String, que especificam dois nós da árvore através dos seus valores. Deve devolver o caminho mais curto na árvore do primeiro até ao segundo nó.

Mensagens de exceção

Por vezes é necessário lançar uma exceção. Quando o fazes, deves incluir sempre uma mensagem de erro significativa para indicar qual é a origem do erro. Isso torna o teu código mais legível e ajuda imenso a fazer debug.

Este exercício em particular exige que uses a palavra-chave throw para "lançar" várias UnsupportedOperationException se à classe Tree() for passada uma árvore que não pode ser reorientada, ou se não for possível encontrar um caminho entre um start node e um end node. Os testes só passam se fizeres throw da exception e incluíres uma mensagem com ela.

Para lançar uma UnsupportedOperationException com uma mensagem, escreve a mensagem como argumento do 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

Adaptação de um exercício do 4clojure