視点

説明

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

ツリーは特殊なグラフの一種で、すべてのノードがつながっていますが、閉路はありません。 つまり、どの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つのノードの視点から向きを変えます。

---

出典

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