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 programa de testes cria árvores aplicando repetidamente a função variádica New. Por exemplo, a instrução

tree := New("a",New("b"),New("c",New("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 Value e Children serão usados pelo programa de testes para desconstruir as árvores.

A construção e a desconstrução básicas da árvore precisam estar funcionando antes de você começar a parte interessante do exercício, por isso elas são testadas separadamente nos três primeiros testes.

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ó da árvore por meio do 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, fica livre para consumir ou destruir a árvore original. É claro que é legal deixá-la sem modificações.

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

---

Fonte

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