Utasítások
Helyezd át a fa gyökerét egy kiválasztott csomópontra.
A fa a gráf egy speciális fajtája, amelyben minden csomópont össze van kötve, de nincsenek benne körök.
Ez azt jelenti, hogy bármely két csomópont között pontosan egy útvonal vezet az egyiktől a másikig.
Ebben a feladatban arról van szó, hogy újraorientálunk egy fát, hogy más nézőpontból lássuk a dolgokat.
A családfákat például általában az ős szemszögéből szokás bemutatni:
+------0------+
| | |
+-1-+ +-2-+ +-3-+
| | | | | |
4 5 6 7 8 9
De egy fában nincs eleve adott irány.
Ugyanazt az információt a fa bármelyik másik csomópontjának szemszögéből be lehet mutatni úgy, hogy azt húzzuk fel a gyökér helyére, és magával húzzuk a kapcsolatait is.
Így ugyanaz a fa a 6 szemszögéből így nézne ki:
6
|
+-----2-----+
| |
7 +-----0-----+
| |
+-1-+ +-3-+
| | | |
4 5 8 9
Ez lehetővé teszi, hogy egyszerűbben írjuk le a két csomópont közötti útvonalakat.
A 6-9 útvonal például (amely az első fában felmegy a gyökérhez, majd le egy másik levélcsomóponthoz) láthatóan a 6-2-0-3-9 útvonalat követi.
Ez a feladat abból áll, hogy veszünk egy bemeneti fát, és újraorientáljuk az egyik csomópont nézőpontjából.
Megvalósítási megjegyzések
A fa objektumnak két attribútuma van:
-
String label
-
List<Tree> children
A tesztprogram fákat hoz létre a Tree.of építőfüggvény ismételt alkalmazásával.
Például a következő utasítás
Tree tree = Tree.of("a", List.of(Tree.of("b"), Tree.of("c", List.of(Tree.of("d")))));
a következő fát állítja elő:
"a"
|
-------
| |
"b" "c"
|
"d"
Feltételezheted, hogy a tesztfákban nem lesznek ismétlődő értékek.
A feladat érdekes része a FromPov és a PathTo metódus.
A FromPov metódus egy from string argumentumot kap, amely az értékével kijelöl egy
csomópontot a fában. Egy olyan fát kell visszaadnia, amelynek a gyökerében a from érték
áll. Az eredeti fát módosíthatod, és visszaadhatod azt, vagy létrehozhatsz egy új fát, és
visszaadhatod azt. Ha új fát adsz vissza, nyugodtan felhasználhatod vagy
megsemmisítheted az eredetit. Persze az a szép, ha érintetlenül hagyod.
A PathTo metódus két string argumentumot kap, a from és a to értéket, amelyek az
értékük alapján két csomópontot jelölnek ki a fában. A fában az első csomóponttól a
másodikig vezető legrövidebb utat kell visszaadnia.
Kivételüzenetek
Néha szükség van arra, hogy kivételt dobj.
Ilyenkor mindig adj meg egy beszédes hibaüzenetet, amely megmutatja, mi a hiba
forrása. Ettől olvashatóbb lesz a kódod, és a hibakeresésben is sokat segít.
Ennél a feladatnál a throw kulcsszó
segítségével kell „dobnod” több UnsupportedOperationException kivételt, ha a Tree() osztálynak
olyan fát adsz át, amelyet nem lehet újraorientálni, vagy ha nem található út a start node és
az end node között.
A tesztek csak akkor futnak át, ha throw-olod az exception-t, és üzenetet is fűzöl hozzá.
Ha üzenettel szeretnél UnsupportedOperationException kivételt dobni, írd az üzenetet az
exception típus argumentumaként:
// 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");
