Ponto de vista

Instruções

Reparente uma árvore em um nó selecionado.

Uma árvore é um tipo especial de grafo em que todos os nós estão conectados, mas não há ciclos. Isso significa que, para qualquer par de nós, existe exatamente um caminho para ir de um nó até o outro.

Este exercício é sobre reorientar uma árvore para ver as coisas de um ponto de vista diferente. Por exemplo, árvores genealógicas geralmente são apresentadas da perspectiva do ancestral:

    +------0------+
    |      |      |
  +-1-+  +-2-+  +-3-+
  |   |  |   |  |   |
  4   5  6   7  8   9

Mas não existe uma direção inerente em uma árvore. As mesmas informações podem ser apresentadas da perspectiva de qualquer outro nó da árvore, puxando-o até a raiz e arrastando as suas relações junto com ele. Então a mesma árvore da perspectiva do 6 ficaria assim:

        6
        |
  +-----2-----+
  |           |
  7     +-----0-----+
        |           |
      +-1-+       +-3-+
      |   |       |   |
      4   5       8   9

Isso nos permite descrever de forma mais simples os caminhos entre dois nós. Assim, por exemplo, o caminho de 6 a 9 (que na primeira árvore sobe até a raiz e depois desce até outro nó folha) pode ser visto seguindo o caminho 6-2-0-3-9.

Este exercício envolve pegar uma árvore de entrada e reorientá-la do ponto de vista de um dos nós.

Notas de implementação

O objeto Tree tem dois atributos:

• rótulo String
• filhos List<Tree>

O programa de teste cria árvores aplicando repetidamente a 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"

Você pode 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 string from, que especifica um nó na árvore pelo seu valor. Ele deve retornar uma árvore com o valor from na raiz. Você pode modificar a árvore original e retorná-la, ou criar uma nova árvore e retorná-la. Se você retornar uma nova árvore, fique à vontade para consumir ou destruir a árvore original. Claro que o ideal é deixá-la sem modificações.

O método PathTo recebe dois argumentos string, from e to, que especificam dois nós na árvore pelos seus valores. Ele deve retornar o caminho mais curto na árvore do primeiro até o segundo nó.

Mensagens de exceção

Às vezes é necessário lançar uma exceção. Quando fizer isso, sempre inclua uma mensagem de erro significativa para indicar qual é a origem do erro. Isso deixa seu código mais legível e ajuda muito na depuração.

Este exercício específico exige que você use a palavra-chave throw para "lançar" várias UnsupportedOperationException se a classe Tree() receber 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ó vão passar se você throw a exception e incluir uma mensagem junto com ela.

Para lançar uma UnsupportedOperationException com uma mensagem, escreva 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