視点

説明

選んだノードを根として、ツリーの親子関係を組み替えます。

ツリーは特殊なグラフの一種で、すべてのノードがつながっていますが、閉路はありません。 つまり、どの2つのノードの間にも、経路がちょうど1つだけあります。

この演習のテーマは、ツリーの向きを変えて、別の視点から物事を見ることです。 たとえば、家系図はふつう、先祖の視点から表されます。

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

しかし、ツリーにもともと決まった向きはありません。 ツリー内のほかの任意のノードを根に引き上げ、そのつながりも一緒に動かせば、同じ情報でも、そのノードの視点から表すことができます。 すると、同じツリーを6の視点から見ると、次のようになります。

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

こうすると、2つのノードの間の経路を、より簡単に説明できるようになります。 たとえば、6から9への経路（最初のツリーでは、いったん根まで上がってから別の葉ノードへ下っていく経路）は、6-2-0-3-9という経路をたどっていることがわかります。

この演習では、入力として与えられたツリーを、どれか1つのノードの視点から向きを変えます。

実装上の注意

テストプログラムは、可変長のNew関数を繰り返し適用して木を構築します。 たとえば、次の文は

tree := New("a",New("b"),New("c",New("d")))

次の木を構築します。

      "a"
       |
    -------
    |     |
   "b"   "c"
          |
         "d"

テスト用の木に重複した値はないと考えてかまいません。

テストプログラムは、木を分解するためにValueメソッドとChildrenメソッドを使います。

演習の面白い部分に取りかかる前に、基本的な木の構築と分解が動いている必要があります。そのため、最初の3つのテストで個別にテストされます。

FromPovメソッドとPathToメソッドが、この演習の面白い部分です。

FromPovメソッドは、文字列の引数fromを取ります。この引数は、値によって木の中のノードを指定します。 値fromをルートに持つ木を返す必要があります。 元の木を変更してそれを返しても、新しい木を作ってそれを返してもかまいません。 新しい木を返す場合、元の木を自由に消費したり破壊したりできます。 もちろん、元の木を変更せずに残しておくのもよいでしょう。

PathToメソッドは、2つの文字列の引数fromとtoを取ります。これらは、値によって木の中の2つのノードを指定します。 1つ目のノードから2つ目のノードへの、木の中の最短経路を返す必要があります。

---

出典

4clojureの演習を翻案したものです。