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 específicas do exercício em Rust

Tens liberdade para escolher a representação interna da tua árvore. No entanto, tem cuidado se guardares os filhos num contentor ordenado. Duas árvores têm de ser consideradas iguais, independentemente da ordem dos filhos.

---

Fonte

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