以選定的節點重新指定整棵樹的父節點。
樹是一種特殊的圖,其中所有節點都互相連通,但沒有任何環。 也就是說,任兩個節點之間都恰好只有一條路徑。
這個練習的重點,就是把樹重新定向,讓我們能從不同的角度來看待它。 舉例來說,家族樹通常是從祖先的角度來呈現:
+------0------+
| | |
+-1-+ +-2-+ +-3-+
| | | | | |
4 5 6 7 8 9
但樹本身其實並沒有固定的方向。 同一份資訊,也可以從樹中任何其他節點的角度來呈現:只要把那個節點拉到根部,並讓它的關係一起跟著移動就行了。 所以同一棵樹,從 6 的角度來看會變成這樣:
6
|
+-----2-----+
| |
7 +-----0-----+
| |
+-1-+ +-3-+
| | | |
4 5 8 9
這樣一來,我們就能更簡單地描述兩個節點之間的路徑。 舉例來說,從 6 到 9 的路徑(在第一棵樹裡,這條路徑會先往上到根部,再往下走到另一個葉節點),可以看出它依序經過 6-2-0-3-9。
這個練習會拿到一棵輸入的樹,並從其中某個節點的角度將它重新定向。
樹狀物件有兩個屬性:
String標籤List<Tree>子節點測試程式會透過反覆套用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方法接受兩個字串引數from和to,用來透過值指定樹中的兩個節點。它應該回傳樹中從第一個節點到第二個節點的最短路徑。
有時候必須拋出例外。
當你這麼做時,應該一律附上有意義的錯誤訊息,指出錯誤的來源。這能讓你的程式碼更容易閱讀,對除錯也有很大的幫助。
這個練習特別要求你使用throw 關鍵字,在Tree()類別被傳入無法重新定向的樹,或是在start node和end node之間找不到路徑時,「拋出」多個UnsupportedOperationException。你必須同時throw這個exception並附上訊息,測試才會通過。
若要拋出帶有訊息的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");