POV

POV

困難

說明

以選定的節點重新指定整棵樹的父節點。

樹是一種特殊的圖,其中所有節點都互相連通,但沒有任何環。 也就是說,任兩個節點之間都恰好只有一條路徑。

這個練習的重點,就是把樹重新定向,讓我們能從不同的角度來看待它。 舉例來說,家族樹通常是從祖先的角度來呈現:

    +------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");
透過 GitHub 編輯 連結會在新視窗或分頁中開啟
Java Exercism

準備好開始 POV 了嗎?

註冊 Exercism,透過 26 個概念158 個練習 和真人引導來學習並精通 Java,全部免費。