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 tesztprogram fákat hoz létre úgy, hogy ismételten meghívja a variadikus New függvényt.
Például az alábbi utasítás
tree := New("a",New("b"),New("c",New("d")))
a következő fát építi fel:
"a"
|
-------
| |
"b" "c"
|
"d"
Feltételezheted, hogy a tesztfákban nem lesznek ismétlődő értékek.
A tesztprogram a Value és a Children metódust használja majd a fák szétbontásához.
A fa alapvető felépítésének és szétbontásának már működnie kell, mielőtt nekilátsz a feladat érdekes részének, ezért ezt külön teszteli az első három teszt.
A FromPov és a PathTo metódus a feladat érdekes része.
A FromPov metódus egy from string argumentumot kap, amely az értékével jelöl ki egy csomópontot a fában.
Egy olyan fát kell visszaadnia, amelynek a gyökerében a from érték áll.
Módosíthatod az eredeti fát és visszaadhatod azt, vagy létrehozhatsz egy új fát és visszaadhatod azt.
Ha új fát adsz vissza, nyugodtan felhasználhatod vagy elpusztíthatod az eredetit.
Persze az a szép, ha érintetlenül hagyod.
A PathTo metódus két string argumentumot kap, from és to néven, amelyek az értékükkel 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.
