Tehtävien deadline: ma 23.2. klo 01:59
Viikon teemana on erilasiten metodien toteuttaminen binääripuille. Rekursiosta on erittäin paljon hyötyä! Mahdollisesti hyödyllienen esimerkki.
Sinulle on annettu binääripuu ja tehtäväsi on laskea, montako kertaa arvo x esiintyy puussa.
Toteuta seuraava metodi:
int laskeArvot(Puu puu, int x)
Parametri puu
on binääripuu,
jossa on 1..105 solmua.
Parametri x
on etsittävä arvo.
Metodin tulee palauttaa,
montako kertaa x
esiintyy puussa.
Seuraava koodi testaa metodia:
Puu puu = new Puu(1, new Puu(3, new Puu(2, null, null), null), new Puu(3, new Puu(3, null, null), new Puu(2, null, null))); System.out.println(laskeArvot(puu, 1)); System.out.println(laskeArvot(puu, 2)); System.out.println(laskeArvot(puu, 3));
Koodin tulostuksen tulisi olla seuraava:
1 2 3
Sinulle on annettu binääripuu ja tehtäväsi on tutkia, onko puu täydellinen, eli onko jokainen polku juuresta alaspäin yhtä pitkä.
Toteuta seuraava metodi:
boolean taydellinen(Puu puu)
Parametri puu
on binääripuu,
jossa on 1..105 solmua.
Metodin tulee palauttaa
true
, jos puu on täydellinen,
ja muuten false
.
Seuraava koodi testaa metodia:
Puu puu = new Puu(1, new Puu(3, new Puu(2, null, null), new Puu(1, null, null)), new Puu(3, new Puu(3, null, null), new Puu(2, null, null))); System.out.println(taydellinen(puu));
Koodin tulostuksen tulisi olla seuraava:
true
Sinulle on annettu kaksi binääripuuta, ja tehtäväsi on tutkia, ovatko puun samanlaiset eli onko puiden rakenne samanlainen ja onko niissä samat arvot kaikissa kohdissa.
Toteuta seuraava metodi:
boolean samanlaiset(Puu a, Puu b)
Parametrit a
ja b
ovat tutkittavat binääripuut.
Molemmat sisältävät 1..105 solmua.
Metodin tulee palauttaa
true
, jos puut ovat samanlaiset,
ja muuten false
.
Seuraava koodi testaa metodia:
Puu puu1 = new Puu(1, new Puu(3, new Puu(2, null, null), new Puu(1, null, null)), new Puu(3, new Puu(3, null, null), new Puu(2, null, null))); Puu puu2 = new Puu(1, new Puu(3, new Puu(2, null, null), new Puu(1, null, null)), new Puu(3, new Puu(3, null, null), new Puu(2, null, null))); System.out.println(samanlaiset(puu1, puu2));
Koodin tulostuksen tulisi olla seuraava:
true
Tiedetään, että puussa jokaisen solmuparin välillä on yksikäsitteinen polku, joka kulkee enintään kerran minkään solun läpi. Tehtävänäsi on etsiä pisin mahdollinen tällaisen polun pituus puusta, joka annetaan syötteenä.
Toteuta seuraava metodi:
int pisinPolku(Puu puu)
Parametri puu
on binääripuu,
jossa on 1..105 solmua.
Metodin tulee palauttaa pisimmän polun pituus jonkin kahden solmun välillä.
Seuraava koodi testaa metodia:
Puu puu = new Puu(1, new Puu(3, new Puu(2, null, null), null), new Puu(3, new Puu(3, null, null), new Puu(2, null, null))); System.out.println(pisinPolku(puu));
Koodin tulostuksen tulisi olla seuraava:
4
Sinulle on annettu binääripuun esi- ja sisäjärjestys. Tehtäväsi on muodostaa niiden perusteella jälkijärjestys.
Esijärjestys käy ensin puun juuressa, sitten vasemmassa alipuussa ja lopuksi oikeassa alipuussa. Sisäjärjestys käy ensin vasemmassa alipuussa, sitten puun juuressa ja lopuksi oikeassa alipuussa. Jälkijärjestys käy ensin vasemmassa alipuussa, sitten oikeassa alipuussa ja lopuksi puun juuressa.
Esimerkiksi binääripuuta
B / \ D A / \ C E
vastaa esijärjestys BDACE, sisäjärjestys DBCAE ja jälkijärjestys DCEAB.
Toteuta seuraava metodi:
String jalki(String esi, String sisa)
Parametrit esi
ja sisa
kuvaavat binääripuun esi- ja sisäjärjestyksen.
Binääripuussa on 1..26 solmua ja niiden tunnukset
ovat suuret kirjaimet A:sta lähtien.
Metodin tulee palauttaa binääripuun jälkijärjestys vastaavassa muodossa.
# | metodin kutsu | haluttu palautusarvo |
---|---|---|
1 | jalki("BDACE", "DBCAE") | "DCEAB" |
2 | jalki("ABCD", "DCBA") | "DCBA" |
3 | jalki("ABCD", "ACDB") | "DCBA" |
4 | jalki("GEABFCD", "AEBGCFD") | "ABECDFG" |