Helsingin yliopisto, University of Helsinki
MOOC.FI

Viikko 6

Viikon teemana on erilasiten metodien toteuttaminen binääripuille. Rekursiosta on erittäin paljon hyötyä! Mahdollisesti hyödyllienen esimerkki.

Tehtävä 1

Sinulle on annettu binääripuu ja tehtäväsi on laskea, montako kertaa arvo x esiintyy puussa.

Toteutus

Toteuta metodi: int laskeArvot(Puu puu, int x)

Parametri puu on binääripuu, jossa on 1..10 5 solmua. Parametri x on etsittävä arvo.

Metodin tulee palauttaa, montako kertaa x esiintyy puussa.

Esimerkit

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

Tehtävä 2

Sinulle on annettu binääripuu ja tehtäväsi on tutkia, onko puu täydellinen, eli onko jokainen polku juuresta alaspäin yhtä pitkä.

Toteutus

Toteuta metodi: boolean taydellinen(Puu puu)

Parametri puu on binääripuu, jossa on 1..10 5 solmua.

Metodin tulee palauttaa true , jos puu on täydellinen, ja muuten false .

Esimerkit

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

Tehtävä 3

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.

Toteutus

Toteuta metodi: boolean samanlaiset(Puu a, Puu b)

Parametrit a ja b ovat tutkittavat binääripuut. Molemmat sisältävät 1..10 5 solmua.

Metodin tulee palauttaa true , jos puut ovat samanlaiset, ja muuten false .

Esimerkit

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

Tehtävä 4

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ä.

Toteutus

Toteuta metodi: int pisinPolku(Puu puu)

Parametri puu on binääripuu, jossa on 1..10 5 solmua.

Metodin tulee palauttaa pisimmän polun pituus jonkin kahden solmun välillä.

Esimerkit

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

Tehtävä 5

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.

Toteutus

Toteuta 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.

Esimerkit

# metodin kutsu haluttu palautusarvo
1 jalki("BDACE", "DBCAE") "DCEAB"
2 jalki("ABCD", "DCBA") "DCBA"
3 jalki("ABCD", "ACDB") "DCBA"
4 jalki("GEABFCD", "AEBGCFD") "ABECDFG"