説明
選んだノードを根として、ツリーの親子関係を組み替えます。
ツリーは特殊なグラフの一種で、すべてのノードがつながっていますが、閉路はありません。
つまり、どの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つのノードの視点から向きを変えます。
実装メモ
Treeオブジェクトには2つの属性があります。
-
String label
-
List<Tree> children
テストプログラムは、ビルダー関数Tree.ofを繰り返し適用してツリーを作ります。たとえば、次の文は
Tree tree = Tree.of("a", List.of(Tree.of("b"), Tree.of("c", List.of(Tree.of("d")))));
次のツリーを構築します。
"a"
|
-------
| |
"b" "c"
|
"d"
テスト用のツリーに重複した値はないと想定してかまいません。
メソッドFromPovとPathToが、この演習の面白いところです。
メソッドFromPovは、文字列の引数fromを受け取ります。これはツリー内のノードをその値で指定するものです。fromの値を持つノードを根にしたツリーを返す必要があります。元のツリーを変更してそのまま返しても、新しいツリーを作って返してもかまいません。新しいツリーを返す場合は、元のツリーを消費したり破棄したりしても自由です。もちろん、変更せずにそのままにしておくのが望ましいですが。
メソッドPathToは、2つの文字列の引数fromとtoを受け取ります。これらはツリー内の2つのノードをその値で指定するものです。1つ目のノードから2つ目のノードへの、ツリー内で最も短い経路を返す必要があります。
例外メッセージ
例外をスローする必要がある場合があります。スローするときは、エラーの原因を示す意味のあるエラーメッセージを必ず含めてください。これによりコードが読みやすくなり、デバッグが格段に楽になります。
この演習では、throwキーワードを使って、Tree()クラスに方向を変えられないツリーが渡された場合や、start nodeとend nodeの間に経路が見つからない場合に、複数のUnsupportedOperationExceptionを「スロー」する必要があります。テストは、exceptionをthrowし、それにメッセージを添えた場合にのみ通ります。
メッセージ付きでUnsupportedOperationExceptionをスローするには、メッセージを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");
